<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en"><head>

<meta charset="utf-8">
<meta name="generator" content="quarto-1.7.33">

<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes">


<title>11&nbsp; Data Structures – Introduction to Zig</title>
<style>
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
div.columns{display: flex; gap: min(4vw, 1.5em);}
div.column{flex: auto; overflow-x: auto;}
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
ul.task-list{list-style: none;}
ul.task-list li input[type="checkbox"] {
  width: 0.8em;
  margin: 0 0.8em 0.2em -1em; /* quarto-specific, see https://github.com/quarto-dev/quarto-cli/issues/4556 */ 
  vertical-align: middle;
}
/* CSS for syntax highlighting */
html { -webkit-text-size-adjust: 100%; }
pre > code.sourceCode { white-space: pre; position: relative; }
pre > code.sourceCode > span { display: inline-block; line-height: 1.25; }
pre > code.sourceCode > span:empty { height: 1.2em; }
.sourceCode { overflow: visible; }
code.sourceCode > span { color: inherit; text-decoration: inherit; }
div.sourceCode { margin: 1em 0; }
pre.sourceCode { margin: 0; }
@media screen {
div.sourceCode { overflow: auto; }
}
@media print {
pre > code.sourceCode { white-space: pre-wrap; }
pre > code.sourceCode > span { text-indent: -5em; padding-left: 5em; }
}
pre.numberSource code
  { counter-reset: source-line 0; }
pre.numberSource code > span
  { position: relative; left: -4em; counter-increment: source-line; }
pre.numberSource code > span > a:first-child::before
  { content: counter(source-line);
    position: relative; left: -1em; text-align: right; vertical-align: baseline;
    border: none; display: inline-block;
    -webkit-touch-callout: none; -webkit-user-select: none;
    -khtml-user-select: none; -moz-user-select: none;
    -ms-user-select: none; user-select: none;
    padding: 0 4px; width: 4em;
  }
pre.numberSource { margin-left: 3em;  padding-left: 4px; }
div.sourceCode
  {   }
@media screen {
pre > code.sourceCode > span > a:first-child::before { text-decoration: underline; }
}
/* CSS for citations */
div.csl-bib-body { }
div.csl-entry {
  clear: both;
  margin-bottom: 0em;
}
.hanging-indent div.csl-entry {
  margin-left:2em;
  text-indent:-2em;
}
div.csl-left-margin {
  min-width:2em;
  float:left;
}
div.csl-right-inline {
  margin-left:2em;
  padding-left:1em;
}
div.csl-indent {
  margin-left: 2em;
}</style>


<script src="../site_libs/quarto-nav/quarto-nav.js"></script>
<script src="../site_libs/quarto-nav/headroom.min.js"></script>
<script src="../site_libs/clipboard/clipboard.min.js"></script>
<script src="../site_libs/quarto-search/autocomplete.umd.js"></script>
<script src="../site_libs/quarto-search/fuse.min.js"></script>
<script src="../site_libs/quarto-search/quarto-search.js"></script>
<meta name="quarto:offset" content="../">
<link href="../Chapters/10-stack-project.html" rel="next">
<link href="../Chapters/09-error-handling.html" rel="prev">
<script src="../site_libs/quarto-html/quarto.js" type="module"></script>
<script src="../site_libs/quarto-html/tabsets/tabsets.js" type="module"></script>
<script src="../site_libs/quarto-html/popper.min.js"></script>
<script src="../site_libs/quarto-html/tippy.umd.min.js"></script>
<script src="../site_libs/quarto-html/anchor.min.js"></script>
<link href="../site_libs/quarto-html/tippy.css" rel="stylesheet">
<link href="../site_libs/quarto-html/quarto-syntax-highlighting-59898bd1c6b9d2bb783127feaa000c76.css" rel="stylesheet" class="quarto-color-scheme" id="quarto-text-highlighting-styles">
<link href="../site_libs/quarto-html/quarto-syntax-highlighting-dark-d329e753491efaeac79c98c4b193a686.css" rel="stylesheet" class="quarto-color-scheme quarto-color-alternate" id="quarto-text-highlighting-styles">
<link href="../site_libs/quarto-html/quarto-syntax-highlighting-59898bd1c6b9d2bb783127feaa000c76.css" rel="stylesheet" class="quarto-color-scheme-extra" id="quarto-text-highlighting-styles">
<script src="../site_libs/bootstrap/bootstrap.min.js"></script>
<link href="../site_libs/bootstrap/bootstrap-icons.css" rel="stylesheet">
<link href="../site_libs/bootstrap/bootstrap-5a7d69291c2a8c67bc3a157f4354e263.min.css" rel="stylesheet" append-hash="true" class="quarto-color-scheme" id="quarto-bootstrap" data-mode="light">
<link href="../site_libs/bootstrap/bootstrap-dark-a459d9a911ec262923466a12d18bc01e.min.css" rel="stylesheet" append-hash="true" class="quarto-color-scheme quarto-color-alternate" id="quarto-bootstrap" data-mode="dark">
<link href="../site_libs/bootstrap/bootstrap-5a7d69291c2a8c67bc3a157f4354e263.min.css" rel="stylesheet" append-hash="true" class="quarto-color-scheme-extra" id="quarto-bootstrap" data-mode="light">
<script id="quarto-search-options" type="application/json">{
  "location": "sidebar",
  "copy-button": false,
  "collapse-after": 3,
  "panel-placement": "start",
  "type": "textbox",
  "limit": 50,
  "keyboard-shortcut": [
    "f",
    "/",
    "s"
  ],
  "show-item-context": false,
  "language": {
    "search-no-results-text": "No results",
    "search-matching-documents-text": "matching documents",
    "search-copy-link-title": "Copy link to search",
    "search-hide-matches-text": "Hide additional matches",
    "search-more-match-text": "more match in this document",
    "search-more-matches-text": "more matches in this document",
    "search-clear-button-title": "Clear",
    "search-text-placeholder": "",
    "search-detached-cancel-button-title": "Cancel",
    "search-submit-button-title": "Submit",
    "search-label": "Search"
  }
}</script>
<script async="" src="https://www.googletagmanager.com/gtag/js?id=G-6CHJXK4CEV"></script>

<script type="text/javascript">

window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-6CHJXK4CEV', { 'anonymize_ip': true});
</script>

  <script src="https://cdnjs.cloudflare.com/polyfill/v3/polyfill.min.js?features=es6"></script>
  <script src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-chtml-full.js" type="text/javascript"></script>

<script type="text/javascript">
const typesetMath = (el) => {
  if (window.MathJax) {
    // MathJax Typeset
    window.MathJax.typeset([el]);
  } else if (window.katex) {
    // KaTeX Render
    var mathElements = el.getElementsByClassName("math");
    var macros = [];
    for (var i = 0; i < mathElements.length; i++) {
      var texText = mathElements[i].firstChild;
      if (mathElements[i].tagName == "SPAN") {
        window.katex.render(texText.data, mathElements[i], {
          displayMode: mathElements[i].classList.contains('display'),
          throwOnError: false,
          macros: macros,
          fleqn: false
        });
      }
    }
  }
}
window.Quarto = {
  typesetMath
};
</script>

</head>

<body class="nav-sidebar floating quarto-light"><script id="quarto-html-before-body" type="application/javascript">
    const toggleBodyColorMode = (bsSheetEl) => {
      const mode = bsSheetEl.getAttribute("data-mode");
      const bodyEl = window.document.querySelector("body");
      if (mode === "dark") {
        bodyEl.classList.add("quarto-dark");
        bodyEl.classList.remove("quarto-light");
      } else {
        bodyEl.classList.add("quarto-light");
        bodyEl.classList.remove("quarto-dark");
      }
    }
    const toggleBodyColorPrimary = () => {
      const bsSheetEl = window.document.querySelector("link#quarto-bootstrap:not([rel=disabled-stylesheet])");
      if (bsSheetEl) {
        toggleBodyColorMode(bsSheetEl);
      }
    }
    const setColorSchemeToggle = (alternate) => {
      const toggles = window.document.querySelectorAll('.quarto-color-scheme-toggle');
      for (let i=0; i < toggles.length; i++) {
        const toggle = toggles[i];
        if (toggle) {
          if (alternate) {
            toggle.classList.add("alternate");
          } else {
            toggle.classList.remove("alternate");
          }
        }
      }
    };
    const toggleColorMode = (alternate) => {
      // Switch the stylesheets
      const primaryStylesheets = window.document.querySelectorAll('link.quarto-color-scheme:not(.quarto-color-alternate)');
      const alternateStylesheets = window.document.querySelectorAll('link.quarto-color-scheme.quarto-color-alternate');
      manageTransitions('#quarto-margin-sidebar .nav-link', false);
      if (alternate) {
        // note: dark is layered on light, we don't disable primary!
        enableStylesheet(alternateStylesheets);
        for (const sheetNode of alternateStylesheets) {
          if (sheetNode.id === "quarto-bootstrap") {
            toggleBodyColorMode(sheetNode);
          }
        }
      } else {
        disableStylesheet(alternateStylesheets);
        enableStylesheet(primaryStylesheets)
        toggleBodyColorPrimary();
      }
      manageTransitions('#quarto-margin-sidebar .nav-link', true);
      // Switch the toggles
      setColorSchemeToggle(alternate)
      // Hack to workaround the fact that safari doesn't
      // properly recolor the scrollbar when toggling (#1455)
      if (navigator.userAgent.indexOf('Safari') > 0 && navigator.userAgent.indexOf('Chrome') == -1) {
        manageTransitions("body", false);
        window.scrollTo(0, 1);
        setTimeout(() => {
          window.scrollTo(0, 0);
          manageTransitions("body", true);
        }, 40);
      }
    }
    const disableStylesheet = (stylesheets) => {
      for (let i=0; i < stylesheets.length; i++) {
        const stylesheet = stylesheets[i];
        stylesheet.rel = 'disabled-stylesheet';
      }
    }
    const enableStylesheet = (stylesheets) => {
      for (let i=0; i < stylesheets.length; i++) {
        const stylesheet = stylesheets[i];
        if(stylesheet.rel !== 'stylesheet') { // for Chrome, which will still FOUC without this check
          stylesheet.rel = 'stylesheet';
        }
      }
    }
    const manageTransitions = (selector, allowTransitions) => {
      const els = window.document.querySelectorAll(selector);
      for (let i=0; i < els.length; i++) {
        const el = els[i];
        if (allowTransitions) {
          el.classList.remove('notransition');
        } else {
          el.classList.add('notransition');
        }
      }
    }
    const isFileUrl = () => {
      return window.location.protocol === 'file:';
    }
    const hasAlternateSentinel = () => {
      let styleSentinel = getColorSchemeSentinel();
      if (styleSentinel !== null) {
        return styleSentinel === "alternate";
      } else {
        return false;
      }
    }
    const setStyleSentinel = (alternate) => {
      const value = alternate ? "alternate" : "default";
      if (!isFileUrl()) {
        window.localStorage.setItem("quarto-color-scheme", value);
      } else {
        localAlternateSentinel = value;
      }
    }
    const getColorSchemeSentinel = () => {
      if (!isFileUrl()) {
        const storageValue = window.localStorage.getItem("quarto-color-scheme");
        return storageValue != null ? storageValue : localAlternateSentinel;
      } else {
        return localAlternateSentinel;
      }
    }
    const toggleGiscusIfUsed = (isAlternate, darkModeDefault) => {
      const baseTheme = document.querySelector('#giscus-base-theme')?.value ?? 'light';
      const alternateTheme = document.querySelector('#giscus-alt-theme')?.value ?? 'dark';
      let newTheme = '';
      if(authorPrefersDark) {
        newTheme = isAlternate ? baseTheme : alternateTheme;
      } else {
        newTheme = isAlternate ? alternateTheme : baseTheme;
      }
      const changeGiscusTheme = () => {
        // From: https://github.com/giscus/giscus/issues/336
        const sendMessage = (message) => {
          const iframe = document.querySelector('iframe.giscus-frame');
          if (!iframe) return;
          iframe.contentWindow.postMessage({ giscus: message }, 'https://giscus.app');
        }
        sendMessage({
          setConfig: {
            theme: newTheme
          }
        });
      }
      const isGiscussLoaded = window.document.querySelector('iframe.giscus-frame') !== null;
      if (isGiscussLoaded) {
        changeGiscusTheme();
      }
    };
    const authorPrefersDark = false;
    const darkModeDefault = authorPrefersDark;
      document.querySelector('link#quarto-text-highlighting-styles.quarto-color-scheme-extra').rel = 'disabled-stylesheet';
      document.querySelector('link#quarto-bootstrap.quarto-color-scheme-extra').rel = 'disabled-stylesheet';
    let localAlternateSentinel = darkModeDefault ? 'alternate' : 'default';
    // Dark / light mode switch
    window.quartoToggleColorScheme = () => {
      // Read the current dark / light value
      let toAlternate = !hasAlternateSentinel();
      toggleColorMode(toAlternate);
      setStyleSentinel(toAlternate);
      toggleGiscusIfUsed(toAlternate, darkModeDefault);
      window.dispatchEvent(new Event('resize'));
    };
    // Switch to dark mode if need be
    if (hasAlternateSentinel()) {
      toggleColorMode(true);
    } else {
      toggleColorMode(false);
    }
  </script>

<div id="quarto-search-results"></div>
  <header id="quarto-header" class="headroom fixed-top">
  <nav class="quarto-secondary-nav">
    <div class="container-fluid d-flex">
      <button type="button" class="quarto-btn-toggle btn" data-bs-toggle="collapse" role="button" data-bs-target=".quarto-sidebar-collapse-item" aria-controls="quarto-sidebar" aria-expanded="false" aria-label="Toggle sidebar navigation" onclick="if (window.quartoToggleHeadroom) { window.quartoToggleHeadroom(); }">
        <i class="bi bi-layout-text-sidebar-reverse"></i>
      </button>
        <nav class="quarto-page-breadcrumbs" aria-label="breadcrumb"><ol class="breadcrumb"><li class="breadcrumb-item"><a href="../Chapters/09-data-structures.html"><span class="chapter-number">11</span>&nbsp; <span class="chapter-title">Data Structures</span></a></li></ol></nav>
        <a class="flex-grow-1" role="navigation" data-bs-toggle="collapse" data-bs-target=".quarto-sidebar-collapse-item" aria-controls="quarto-sidebar" aria-expanded="false" aria-label="Toggle sidebar navigation" onclick="if (window.quartoToggleHeadroom) { window.quartoToggleHeadroom(); }">      
        </a>
      <button type="button" class="btn quarto-search-button" aria-label="Search" onclick="window.quartoOpenSearch();">
        <i class="bi bi-search"></i>
      </button>
    </div>
  </nav>
</header>
<!-- content -->
<div id="quarto-content" class="quarto-container page-columns page-rows-contents page-layout-article">
<!-- sidebar -->
  <nav id="quarto-sidebar" class="sidebar collapse collapse-horizontal quarto-sidebar-collapse-item sidebar-navigation floating overflow-auto">
    <div class="pt-lg-2 mt-2 text-left sidebar-header">
    <div class="sidebar-title mb-0 py-0">
      <a href="../">Introduction to Zig</a> 
        <div class="sidebar-tools-main">
  <a href="" class="quarto-color-scheme-toggle quarto-navigation-tool  px-1" onclick="window.quartoToggleColorScheme(); return false;" title="Toggle dark mode"><i class="bi"></i></a>
</div>
    </div>
      </div>
        <div class="mt-2 flex-shrink-0 align-items-center">
        <div class="sidebar-search">
        <div id="quarto-search" class="" title="Search"></div>
        </div>
        </div>
    <div class="sidebar-menu-container"> 
    <ul class="list-unstyled mt-1">
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../index.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text">Welcome</span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/01-zig-weird.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">1</span>&nbsp; <span class="chapter-title">Introducing Zig</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/03-structs.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">2</span>&nbsp; <span class="chapter-title">Control flow, structs, modules and types</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/01-memory.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">3</span>&nbsp; <span class="chapter-title">Memory and Allocators</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/01-base64.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">4</span>&nbsp; <span class="chapter-title">Project 1 - Building a base64 encoder/decoder</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/02-debugging.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">5</span>&nbsp; <span class="chapter-title">Debugging Zig applications</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/05-pointers.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">6</span>&nbsp; <span class="chapter-title">Pointers and Optionals</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/04-http-server.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">7</span>&nbsp; <span class="chapter-title">Project 2 - Building a HTTP Server from scratch</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/03-unittests.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">8</span>&nbsp; <span class="chapter-title">Unit tests</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/07-build-system.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">9</span>&nbsp; <span class="chapter-title">Build System</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/09-error-handling.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">10</span>&nbsp; <span class="chapter-title">Error handling and unions</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/09-data-structures.html" class="sidebar-item-text sidebar-link active">
 <span class="menu-text"><span class="chapter-number">11</span>&nbsp; <span class="chapter-title">Data Structures</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/10-stack-project.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">12</span>&nbsp; <span class="chapter-title">Project 3 - Building a stack data structure</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/12-file-op.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">13</span>&nbsp; <span class="chapter-title">Filesystem and Input/Output (IO)</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/14-zig-c-interop.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">14</span>&nbsp; <span class="chapter-title">Zig interoperability with C</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/13-image-filter.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">15</span>&nbsp; <span class="chapter-title">Project 4 - Developing an image filter</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/14-threads.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">16</span>&nbsp; <span class="chapter-title">Introducing threads and parallelism in Zig</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/15-vectors.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text"><span class="chapter-number">17</span>&nbsp; <span class="chapter-title">Introducing Vectors and SIMD</span></span></a>
  </div>
</li>
        <li class="sidebar-item">
  <div class="sidebar-item-container"> 
  <a href="../Chapters/references.html" class="sidebar-item-text sidebar-link">
 <span class="menu-text">References</span></a>
  </div>
</li>
    </ul>
    </div>
</nav>
<div id="quarto-sidebar-glass" class="quarto-sidebar-collapse-item" data-bs-toggle="collapse" data-bs-target=".quarto-sidebar-collapse-item"></div>
<!-- margin-sidebar -->
    <div id="quarto-margin-sidebar" class="sidebar margin-sidebar">
        <nav id="TOC" role="doc-toc" class="toc-active">
    <h2 id="toc-title">Table of contents</h2>
   
  <ul>
  <li><a href="#sec-dynamic-array" id="toc-sec-dynamic-array" class="nav-link active" data-scroll-target="#sec-dynamic-array"><span class="header-section-number">11.1</span> Dynamic Arrays</a>
  <ul class="collapse">
  <li><a href="#capacity-vs-length" id="toc-capacity-vs-length" class="nav-link" data-scroll-target="#capacity-vs-length"><span class="header-section-number">11.1.1</span> Capacity vs Length</a></li>
  <li><a href="#creating-an-arraylist-object" id="toc-creating-an-arraylist-object" class="nav-link" data-scroll-target="#creating-an-arraylist-object"><span class="header-section-number">11.1.2</span> Creating an <code>ArrayList</code> object</a></li>
  <li><a href="#adding-new-elements-to-the-array" id="toc-adding-new-elements-to-the-array" class="nav-link" data-scroll-target="#adding-new-elements-to-the-array"><span class="header-section-number">11.1.3</span> Adding new elements to the array</a></li>
  <li><a href="#sec-dynamic-array-remove" id="toc-sec-dynamic-array-remove" class="nav-link" data-scroll-target="#sec-dynamic-array-remove"><span class="header-section-number">11.1.4</span> Removing elements from the array</a></li>
  <li><a href="#inserting-elements-at-specific-indexes" id="toc-inserting-elements-at-specific-indexes" class="nav-link" data-scroll-target="#inserting-elements-at-specific-indexes"><span class="header-section-number">11.1.5</span> Inserting elements at specific indexes</a></li>
  <li><a href="#conclusion" id="toc-conclusion" class="nav-link" data-scroll-target="#conclusion"><span class="header-section-number">11.1.6</span> Conclusion</a></li>
  </ul></li>
  <li><a href="#sec-maps-hashtables" id="toc-sec-maps-hashtables" class="nav-link" data-scroll-target="#sec-maps-hashtables"><span class="header-section-number">11.2</span> Maps or HashTables</a>
  <ul class="collapse">
  <li><a href="#what-is-a-hashtable" id="toc-what-is-a-hashtable" class="nav-link" data-scroll-target="#what-is-a-hashtable"><span class="header-section-number">11.2.1</span> What is a hashtable?</a></li>
  <li><a href="#sec-hashmap" id="toc-sec-hashmap" class="nav-link" data-scroll-target="#sec-hashmap"><span class="header-section-number">11.2.2</span> Hashtables in Zig</a></li>
  <li><a href="#iterating-through-the-hashtable" id="toc-iterating-through-the-hashtable" class="nav-link" data-scroll-target="#iterating-through-the-hashtable"><span class="header-section-number">11.2.3</span> Iterating through the hashtable</a></li>
  <li><a href="#sec-array-map" id="toc-sec-array-map" class="nav-link" data-scroll-target="#sec-array-map"><span class="header-section-number">11.2.4</span> The <code>ArrayHashMap</code> hashtable</a></li>
  <li><a href="#sec-string-hash-map" id="toc-sec-string-hash-map" class="nav-link" data-scroll-target="#sec-string-hash-map"><span class="header-section-number">11.2.5</span> The <code>StringHashMap</code> hashtable</a></li>
  <li><a href="#the-stringarrayhashmap-hashtable" id="toc-the-stringarrayhashmap-hashtable" class="nav-link" data-scroll-target="#the-stringarrayhashmap-hashtable"><span class="header-section-number">11.2.6</span> The <code>StringArrayHashMap</code> hashtable</a></li>
  </ul></li>
  <li><a href="#linked-lists" id="toc-linked-lists" class="nav-link" data-scroll-target="#linked-lists"><span class="header-section-number">11.3</span> Linked lists</a>
  <ul class="collapse">
  <li><a href="#recent-change-in-the-api" id="toc-recent-change-in-the-api" class="nav-link" data-scroll-target="#recent-change-in-the-api"><span class="header-section-number">11.3.1</span> Recent change in the API</a></li>
  <li><a href="#how-to-use-a-singly-linked-list" id="toc-how-to-use-a-singly-linked-list" class="nav-link" data-scroll-target="#how-to-use-a-singly-linked-list"><span class="header-section-number">11.3.2</span> How to use a singly linked list</a></li>
  <li><a href="#how-to-use-a-doubly-linked-list" id="toc-how-to-use-a-doubly-linked-list" class="nav-link" data-scroll-target="#how-to-use-a-doubly-linked-list"><span class="header-section-number">11.3.3</span> How to use a doubly linked list</a></li>
  <li><a href="#iterating-through-the-linked-list" id="toc-iterating-through-the-linked-list" class="nav-link" data-scroll-target="#iterating-through-the-linked-list"><span class="header-section-number">11.3.4</span> Iterating through the linked list</a></li>
  </ul></li>
  <li><a href="#multi-array-structure" id="toc-multi-array-structure" class="nav-link" data-scroll-target="#multi-array-structure"><span class="header-section-number">11.4</span> Multi array structure</a></li>
  <li><a href="#conclusion-1" id="toc-conclusion-1" class="nav-link" data-scroll-target="#conclusion-1"><span class="header-section-number">11.5</span> Conclusion</a></li>
  </ul>
</nav>
    </div>
<!-- main -->
<main class="content" id="quarto-document-content">


<header id="title-block-header" class="quarto-title-block default">
<div class="quarto-title">
<h1 class="title"><span class="chapter-number">11</span>&nbsp; <span class="chapter-title">Data Structures</span></h1>
</div>



<div class="quarto-title-meta">

    
  
    
  </div>
  


</header>


<p>In this chapter, I want to present the most common Data Structures that are available from the Zig Standard Library, especially <code>ArrayList</code> and also <code>HashMap</code>. These are generic Data Structures that you can use to store and control any type of data that is produced by your application.</p>
<section id="sec-dynamic-array" class="level2" data-number="11.1">
<h2 data-number="11.1" class="anchored" data-anchor-id="sec-dynamic-array"><span class="header-section-number">11.1</span> Dynamic Arrays</h2>
<p>In high level languages, arrays are usually dynamic. They can easily grow in size when they have to, and you don’t need to worry about it. In contrast, arrays in low level languages are usually static by default. This is the reality of C, C++, Rust and also Zig. Static arrays were presented at <a href="01-zig-weird.html#sec-arrays" class="quarto-xref"><span>Section 1.6</span></a>, but in this section, we are going to talk about dynamic arrays in Zig.</p>
<p>Dynamic arrays are simply arrays that can grow in size during the runtime of your program. Most low level languages have some implementation of a dynamic array in their standard library. C++ have <code>std::vector</code>, Rust have <code>Vec</code>, and Zig have <code>std.ArrayList</code>.</p>
<p>The <code>std.ArrayList</code> struct provides a contiguous and growable array for you. It works like any other dynamic array, it allocates a contiguous block of memory, and when this block have no space left, <code>ArrayList</code> allocates another contiguous and bigger block of memory, copies the elements to this new location, and erases (or frees) the previous block of memory.</p>
<section id="capacity-vs-length" class="level3" data-number="11.1.1">
<h3 data-number="11.1.1" class="anchored" data-anchor-id="capacity-vs-length"><span class="header-section-number">11.1.1</span> Capacity vs Length</h3>
<p>When we talk about dynamic arrays, we usually have two similar concepts that are very essential to how a dynamic array works behind the hood. These concepts are <em>capacity</em> and <em>length</em>. In some contexts, especially in C++, <em>length</em> is also called of <em>size</em>.</p>
<p>Although they look similar, these concepts represent different things in the context of a dynamic array. <em>Capacity</em> is the number of items (or elements) that your dynamic array can currently hold without the need to allocate more memory.</p>
<p>In contrast, the <em>length</em> refers to how many elements in the array are currently being used, or, in other words, how many elements in this array that you have assigned a value to. Every dynamic array works around a block of allocated memory, which represents an array with total capacity for <span class="math inline">\(n\)</span> elements. However, only a portion of these <span class="math inline">\(n\)</span> elements are being used most of the time. This portion of <span class="math inline">\(n\)</span> is the <em>length</em> of the array. So every time you append a new value to the array, you are incrementing its <em>length</em> by one.</p>
<p>This means that a dynamic array usually works with an extra margin, or an extra space that is currently empty, but waiting and ready to be used. This “extra space” is essentially the difference between <em>capacity</em> and <em>length</em>. <em>Capacity</em> represents the total number of elements that the array can hold without the need to re-allocate or re-expand the array, while the <em>length</em> represents how much of this capacity is currently being used to hold/store values.</p>
<p><a href="#fig-capacity-length" class="quarto-xref">Figure&nbsp;<span>11.1</span></a> presents this idea visually. Notice that, at first, the capacity of the array is greater than the length of the array. So, the dynamic array have extra space that is currently empty, but it is ready to receive a value to be stored.</p>
<div id="fig-capacity-length" class="quarto-float quarto-figure quarto-figure-center anchored">
<figure class="quarto-float quarto-float-fig figure">
<div aria-describedby="fig-capacity-length-caption-0ceaefa1-69ba-4598-a22c-09a6ac19f8ca">
<img src="./../Figures/dynamic-array.png" class="img-fluid figure-img">
</div>
<figcaption class="quarto-float-caption-bottom quarto-float-caption quarto-float-fig" id="fig-capacity-length-caption-0ceaefa1-69ba-4598-a22c-09a6ac19f8ca">
Figure&nbsp;11.1: Difference between capacity and length in a dynamic array
</figcaption>
</figure>
</div>
<p>We can also see in <a href="#fig-capacity-length" class="quarto-xref">Figure&nbsp;<span>11.1</span></a> that, when <em>length</em> and <em>capacity</em> are equal, it means that the array have no space left. We have reached the ceiling of our capacity, and because of that, if we want to store more values in this array, we need to expand it. We need to get a bigger space that can hold more values than what we currently have.</p>
<p>A dynamic array works by expanding the underlying array, whenever the <em>length</em> becomes equal to the <em>capacity</em> of the array. It basically allocates a new contiguous block of memory that is bigger than the previous one, then, it copies all values that are currently being stored to this new location (i.e., this new block of memory), then, it frees the previous block of memory. At the end of this process, the new underlying array have a bigger <em>capacity</em>, and, therefore, the <em>length</em> becomes, once again, smaller than the <em>capacity</em> of the array.</p>
<p>This is the cycle of a dynamic array. Notice that, throughout this cycle, the <em>capacity</em> is always either equal to or higher than the <em>length</em> of the array. If you have an <code>ArrayList</code> object (let’s suppose you named it <code>buffer</code>), you can check the current capacity of your array by accessing the <code>capacity</code> attribute of your <code>ArrayList</code> object, while the current <em>length</em> of it is available at the <code>items.len</code> attribute.</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb1"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb1-1"><a href="#cb1-1" aria-hidden="true" tabindex="-1"></a><span class="co">// Check capacity</span></span>
<span id="cb1-2"><a href="#cb1-2" aria-hidden="true" tabindex="-1"></a>buffer.capacity;</span>
<span id="cb1-3"><a href="#cb1-3" aria-hidden="true" tabindex="-1"></a><span class="co">// Check length</span></span>
<span id="cb1-4"><a href="#cb1-4" aria-hidden="true" tabindex="-1"></a>buffer.items.len;</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
</section>
<section id="creating-an-arraylist-object" class="level3" data-number="11.1.2">
<h3 data-number="11.1.2" class="anchored" data-anchor-id="creating-an-arraylist-object"><span class="header-section-number">11.1.2</span> Creating an <code>ArrayList</code> object</h3>
<p>In order to use <code>ArrayList</code>, you must provide an allocator object to it. Remember, Zig does not have a default memory allocator. And as I described in <a href="01-memory.html#sec-allocators" class="quarto-xref"><span>Section 3.3</span></a>, all memory allocations must be done by an allocator object that you define, that you have control over. In our example here, I’m going to use a general purpose allocator, but you can use any other allocator of your preference.</p>
<p>When you initialize an <code>ArrayList</code> object, you must provide the data type of the elements of the array. In other words, this defines the type of data that this array (or container) will store. Therefore, if I provide the <code>u8</code> type to it, then, I will create a dynamic array of <code>u8</code> values. However, if I provide a struct that I have defined instead, like the struct <code>User</code> from <a href="03-structs.html#sec-structs-and-oop" class="quarto-xref"><span>Section 2.3</span></a>, then, a dynamic array of <code>User</code> values will be created. In the example below, with the expression <code>ArrayList(u8)</code> we are creating a dynamic array of <code>u8</code> values.</p>
<p>After you provide the data type of the elements of the array, you can initialize an <code>ArrayList</code> object by either using the <code>init()</code> or the <code>initCapacity()</code> methods. The former method receives only the allocator object as input, while the latter method receives both the allocator object and a capacity number as inputs. With the latter method, you not only initialize the struct, but you also set the starting capacity of the allocated array.</p>
<p>Using the <code>initCapacity()</code> method is the preferred way to initialize your dynamic array. Because reallocations, or, in other words, the process of expanding the capacity of the array, is always a high cost operation. You should take any possible opportunity to avoid reallocations in your array. If you know how much space your array needs to occupy at the beginning, you should always use <code>initCapacity()</code> to create your dynamic array.</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb2"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb2-1"><a href="#cb2-1" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> gpa = std.heap.GeneralPurposeAllocator(.<span class="op">{}</span>)<span class="op">{}</span>;</span>
<span id="cb2-2"><a href="#cb2-2" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> allocator = gpa.allocator();</span>
<span id="cb2-3"><a href="#cb2-3" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> buffer = <span class="kw">try</span> std.ArrayList(<span class="dt">u8</span>)</span>
<span id="cb2-4"><a href="#cb2-4" aria-hidden="true" tabindex="-1"></a>    .initCapacity(allocator, <span class="dv">100</span>);</span>
<span id="cb2-5"><a href="#cb2-5" aria-hidden="true" tabindex="-1"></a><span class="kw">defer</span> buffer.deinit(allocator);</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<p>In the example above, the <code>buffer</code> object starts as an array of 100 elements. If this <code>buffer</code> object needs to create more space to accomodate more elements during the runtime of your program, the <code>ArrayList</code> internals will perform the necessary actions for you automatically. Also notice the <code>deinit()</code> method being used to destroy the <code>buffer</code> object at the end of the current scope, by freeing all the memory that was allocated for the dynamic array stored in this <code>buffer</code> object.</p>
</section>
<section id="adding-new-elements-to-the-array" class="level3" data-number="11.1.3">
<h3 data-number="11.1.3" class="anchored" data-anchor-id="adding-new-elements-to-the-array"><span class="header-section-number">11.1.3</span> Adding new elements to the array</h3>
<p>Now that we have created our dynamic array, we can start to use it. You can append (a.k.a “add”) new values to this array by using the <code>append()</code> method. This method works the same way as the <code>append()</code> method from a Python list, or, the <code>emplace_back()</code> method from <code>std::vector</code> of C++. You provide a single value to this method, and the method appends this value to the array.</p>
<p>You can also use the <code>appendSlice()</code> method to append multiple values at once. You provide a slice (slices were described in <a href="01-zig-weird.html#sec-arrays" class="quarto-xref"><span>Section 1.6</span></a>) to this method, and the method adds all values present in this slice to your dynamic array.</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb3"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb3-1"><a href="#cb3-1" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> buffer.append(allocator, <span class="ch">'H'</span>);</span>
<span id="cb3-2"><a href="#cb3-2" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> buffer.append(allocator, <span class="ch">'e'</span>);</span>
<span id="cb3-3"><a href="#cb3-3" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> buffer.append(allocator, <span class="ch">'l'</span>);</span>
<span id="cb3-4"><a href="#cb3-4" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> buffer.append(allocator, <span class="ch">'l'</span>);</span>
<span id="cb3-5"><a href="#cb3-5" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> buffer.append(allocator, <span class="ch">'o'</span>);</span>
<span id="cb3-6"><a href="#cb3-6" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> buffer.appendSlice(allocator, <span class="st">" World!"</span>);</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
</section>
<section id="sec-dynamic-array-remove" class="level3" data-number="11.1.4">
<h3 data-number="11.1.4" class="anchored" data-anchor-id="sec-dynamic-array-remove"><span class="header-section-number">11.1.4</span> Removing elements from the array</h3>
<p>You can use the <code>pop()</code> method to “pop” or remove the last element in the array. It’s worth noting that this method do not change the capacity of the array. It just deletes or erases the last value stored in the array.</p>
<p>Also, this method returns as result the value that got deleted. That is, you can use this method to both get the last value in the array, and also, remove it from the array. It’s a “get and remove value” type of method.</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb4"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb4-1"><a href="#cb4-1" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> exclamation_mark = buffer.pop();</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<p>Now, if you want to remove specific elements from specific positions of your array, you can use the <code>orderedRemove()</code> method from your <code>ArrayList</code> object. With this method, you can provide an index as input, then, the method will delete the value that is at this index in the array. You are effectively reducing the <em>length</em> of the array everytime you execute an <code>orderedRemove()</code> operation.</p>
<p>In the example below, we first create an <code>ArrayList</code> object, and we fill it with numbers. Then, we use <code>orderedRemove()</code> to remove the value at index 3 in the array, two consecutive times.</p>
<p>Also, notice that we are assigning the result of <code>orderedRemove()</code> to the underscore character. So we are discarding the result value of this method. The <code>orderedRemove()</code> method returns the value that got deleted, in a similar style to the <code>pop()</code> method.</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb5"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb5-1"><a href="#cb5-1" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> gpa = std.heap.GeneralPurposeAllocator(.<span class="op">{}</span>)<span class="op">{}</span>;</span>
<span id="cb5-2"><a href="#cb5-2" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> allocator = gpa.allocator();</span>
<span id="cb5-3"><a href="#cb5-3" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> buffer = <span class="kw">try</span> std.ArrayList(<span class="dt">u8</span>)</span>
<span id="cb5-4"><a href="#cb5-4" aria-hidden="true" tabindex="-1"></a>    .initCapacity(allocator, <span class="dv">100</span>);</span>
<span id="cb5-5"><a href="#cb5-5" aria-hidden="true" tabindex="-1"></a><span class="kw">defer</span> buffer.deinit(allocator);</span>
<span id="cb5-6"><a href="#cb5-6" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb5-7"><a href="#cb5-7" aria-hidden="true" tabindex="-1"></a><span class="kw">for</span> (<span class="dv">0</span>..<span class="dv">10</span>) |i| <span class="op">{</span></span>
<span id="cb5-8"><a href="#cb5-8" aria-hidden="true" tabindex="-1"></a>    <span class="kw">const</span> index: <span class="dt">u8</span> = <span class="bu">@intCast</span>(i);</span>
<span id="cb5-9"><a href="#cb5-9" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> buffer.append(allocator, index);</span>
<span id="cb5-10"><a href="#cb5-10" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb5-11"><a href="#cb5-11" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb5-12"><a href="#cb5-12" aria-hidden="true" tabindex="-1"></a>std.debug.print(</span>
<span id="cb5-13"><a href="#cb5-13" aria-hidden="true" tabindex="-1"></a>    <span class="st">"{any}</span><span class="sc">\n</span><span class="st">"</span>, .<span class="op">{</span>buffer.items<span class="op">}</span></span>
<span id="cb5-14"><a href="#cb5-14" aria-hidden="true" tabindex="-1"></a>);</span>
<span id="cb5-15"><a href="#cb5-15" aria-hidden="true" tabindex="-1"></a>_ = buffer.orderedRemove(<span class="dv">3</span>);</span>
<span id="cb5-16"><a href="#cb5-16" aria-hidden="true" tabindex="-1"></a>_ = buffer.orderedRemove(<span class="dv">3</span>);</span>
<span id="cb5-17"><a href="#cb5-17" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb5-18"><a href="#cb5-18" aria-hidden="true" tabindex="-1"></a>std.debug.print(<span class="st">"{any}</span><span class="sc">\n</span><span class="st">"</span>, .<span class="op">{</span>buffer.items<span class="op">}</span>);</span>
<span id="cb5-19"><a href="#cb5-19" aria-hidden="true" tabindex="-1"></a>std.debug.print(<span class="st">"{any}</span><span class="sc">\n</span><span class="st">"</span>, .<span class="op">{</span>buffer.items.len<span class="op">}</span>);</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<pre><code>{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
{ 0, 1, 2, 5, 6, 7, 8, 9 }
8</code></pre>
<p>One key characteristic about <code>orderedRemove()</code> is that it preserves the order of the values in the array. So, it deletes the value that you asked it to remove, but it also makes sure that the order of the values that remain in the array stay the same as before.</p>
<p>Now, if you don’t care about the order of the values, for example, maybe you want to treat your dynamic array as a set of values, like the <code>std::unordered_set</code> structure from C++, you can use the <code>swapRemove()</code> method instead. This method works similarly to the <code>orderedRemove()</code> method. You give an index to this method, then, it deletes the value that is at this index in the array. But this method does not preserve the original order of the values that remain in the array. As a result, <code>swapRemove()</code> is, in general, faster than <code>orderedRemove()</code>.</p>
</section>
<section id="inserting-elements-at-specific-indexes" class="level3" data-number="11.1.5">
<h3 data-number="11.1.5" class="anchored" data-anchor-id="inserting-elements-at-specific-indexes"><span class="header-section-number">11.1.5</span> Inserting elements at specific indexes</h3>
<p>When you need to insert values in the middle of your array, instead of just appending them to the end of the array, you need to use the <code>insert()</code> and <code>insertSlice()</code> methods, instead of the <code>append()</code> and <code>appendSlice()</code> methods.</p>
<p>These two methods work very similarly to <code>insert()</code> and <code>insert_range()</code> from the C++ <code>std::vector</code> class. You provide an index to these methods, and they insert the values that you provide at that index in the array.</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb7"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb7-1"><a href="#cb7-1" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> gpa = std.heap.GeneralPurposeAllocator(.<span class="op">{}</span>)<span class="op">{}</span>;</span>
<span id="cb7-2"><a href="#cb7-2" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> allocator = gpa.allocator();</span>
<span id="cb7-3"><a href="#cb7-3" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> buffer = <span class="kw">try</span> std.ArrayList(<span class="dt">u8</span>)</span>
<span id="cb7-4"><a href="#cb7-4" aria-hidden="true" tabindex="-1"></a>    .initCapacity(allocator, <span class="dv">10</span>);</span>
<span id="cb7-5"><a href="#cb7-5" aria-hidden="true" tabindex="-1"></a><span class="kw">defer</span> buffer.deinit(allocator);</span>
<span id="cb7-6"><a href="#cb7-6" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb7-7"><a href="#cb7-7" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> buffer.appendSlice(allocator, <span class="st">"My Pedro"</span>);</span>
<span id="cb7-8"><a href="#cb7-8" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> buffer.insert(allocator, <span class="dv">4</span>, <span class="ch">'3'</span>);</span>
<span id="cb7-9"><a href="#cb7-9" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> buffer.insertSlice(allocator, <span class="dv">2</span>, <span class="st">" name"</span>);</span>
<span id="cb7-10"><a href="#cb7-10" aria-hidden="true" tabindex="-1"></a><span class="kw">for</span> (buffer.items) |char| <span class="op">{</span></span>
<span id="cb7-11"><a href="#cb7-11" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> stdout.print(<span class="st">"{c}"</span>, .<span class="op">{</span>char<span class="op">}</span>);</span>
<span id="cb7-12"><a href="#cb7-12" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb7-13"><a href="#cb7-13" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> stdout.flush();</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<pre><code>My name P3edro</code></pre>
</section>
<section id="conclusion" class="level3" data-number="11.1.6">
<h3 data-number="11.1.6" class="anchored" data-anchor-id="conclusion"><span class="header-section-number">11.1.6</span> Conclusion</h3>
<p>If you feel the lack of some other method, I recommend you to read the <a href="https://ziglang.org/documentation/master/std/#std.array_list.ArrayListAligned">official documentation for the <code>ArrayListAligned</code></a><a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref"><sup>1</sup></a> struct, which describes most of the methods available through the <code>ArrayList</code> object.</p>
<p>You will notice that there is a lot of other methods in this page that I did not described here, and I recommend you to explore these methods, and understand how they work.</p>
</section>
</section>
<section id="sec-maps-hashtables" class="level2" data-number="11.2">
<h2 data-number="11.2" class="anchored" data-anchor-id="sec-maps-hashtables"><span class="header-section-number">11.2</span> Maps or HashTables</h2>
<p>Some professionals know this type of data structure by different terms, like “map”, “hashmap” or “associative arrays”. But the most common term used is <em>hashtable</em>. Every programming language normally have some implementation of a hashtable in their standard libraries. Python have <code>dict()</code>, C++ have <code>std::map</code> and <code>std::unordered_map</code>, Rust have <code>HashMap</code>, Javascript have <code>Object()</code> and <code>Map()</code>, etc.</p>
<section id="what-is-a-hashtable" class="level3" data-number="11.2.1">
<h3 data-number="11.2.1" class="anchored" data-anchor-id="what-is-a-hashtable"><span class="header-section-number">11.2.1</span> What is a hashtable?</h3>
<p>A hashtable is a data structure based on key-value pairs. You provide a key and a value to this structure, then, the hashtable will store the input value at a location that can be identified by the input key that you provided. It does that by using an underlying array and a hash function. These two components are essential to how a hashtable works.</p>
<p>Under the hood, the hashtable contains an array. This array is where the values are stored, and the elements of this array are usually called of <em>buckets</em>. So the values that you provide to the hashtable are stored inside buckets, and you access each bucket by using an index.</p>
<p>When you provide a key to a hashtable, it passes this key to the hash function. This hash function uses some sort of hashing algorithm to transform this key into an index. This index is actually an array index. It’s a position in the underlying array of the hashtable. This is how a key identifies a specific position (or location) inside the hashtable structure.</p>
<p>Therefore, you provide a key to the hashtable, and this key identifies a specific location inside the hashtable, then, the hashtable takes the input value that you provided, and stores this value in the location identified by this input key. You could say that the key maps to the value stored in the hashtable. You find the value, by using the key that identifies the location where the value is stored. The <a href="#fig-hashtable" class="quarto-xref">Figure&nbsp;<span>11.2</span></a> presents this process visually.</p>
<div id="fig-hashtable" class="quarto-float quarto-figure quarto-figure-center anchored">
<figure class="quarto-float quarto-float-fig figure">
<div aria-describedby="fig-hashtable-caption-0ceaefa1-69ba-4598-a22c-09a6ac19f8ca">
<img src="./../Figures/hashtable.svg" class="img-fluid figure-img">
</div>
<figcaption class="quarto-float-caption-bottom quarto-float-caption quarto-float-fig" id="fig-hashtable-caption-0ceaefa1-69ba-4598-a22c-09a6ac19f8ca">
Figure&nbsp;11.2: A diagram of a Hashtable. Source: Wikipedia, the free encyclopedia.
</figcaption>
</figure>
</div>
<p>The operation described in the previous paragraph is normally called an <em>insertion</em> operation. Because you are inserting new values into the hashtable. But there are other types of operations in hashtables such as <em>delete</em> and <em>lookup</em>. Delete is self describing, it’s when you delete (or remove) a value from the hashtable. While lookup corresponds to when you look at a value that is stored in the hashtable, by using the key that identifies the location where this value is stored.</p>
<p>Sometimes, instead of storing the values directly, the underlying array of the hashtable might be an array of pointers, i.e., the buckets of the array stores pointers that points to the value, or also, may be an array of linked lists. These cases are common on hashtables that allows duplicate keys, or, in other words, on hashtables that effectively handle “collisions” that may arise from the hash function.</p>
<p>Duplicate keys, or this “collision” thing that I’m talking about, is when you have two different keys that points to the same location (i.e., to the same index) in the underlying array of the hashtable. This might happen depending on the characteristics of the hash function that is being used in the hashtable. Some implementations of the hashtable will actively deal with collisions, meaning that, they will handle this case in some way. For example, the hashtable might transform all buckets into linked lists. Because with a linked list you can store multiple values into a single bucket.</p>
<p>There are different techniques to handle collisions in hashtables, which I will not describe in this book, because it’s not our main scope here. But you can find a good description of some of the most common techniques at the Wikipedia page of hashtables <span class="citation" data-cites="wikipedia_hashtables">(<a href="references.html#ref-wikipedia_hashtables" role="doc-biblioref">Wikipedia 2024</a>)</span>.</p>
</section>
<section id="sec-hashmap" class="level3" data-number="11.2.2">
<h3 data-number="11.2.2" class="anchored" data-anchor-id="sec-hashmap"><span class="header-section-number">11.2.2</span> Hashtables in Zig</h3>
<p>The Zig Standard Library provides different implementations of a hashtable. Each implementation have its own cons and pros, which we will discuss later on, and all of them are available through the <code>std.hash_map</code> module.</p>
<p>The <code>HashMap</code> struct is a general-purpose hashtable, which have very fast operations (lookup, insertion, delete), and also, quite high load factors for low memory usage. You can create and provide a context object to the <code>HashMap</code> constructor. This context object allows you to tailor the behaviour of the hashtable itself, because you can provide a hash function implementation to be used by the hashtable through this context object.</p>
<p>But let’s not worry about this context object now, because it’s meant to be used by “experts in the field of hashtables”. Since we are most likely not experts in this field, we are going to take the easy way to create a hashtable. Which is by using the <code>AutoHashMap()</code> function.</p>
<p>This <code>AutoHashMap()</code> function is essentially a “create a hashtable object that uses the default settings” type of function. It automatically chooses a context object, and, therefore, a hash function implementation, for you. This function receives two data types as input, the first input is the data type of the keys that will be used in this hashtable, while the second input is the data type of the data that will be stored inside the hashtable, that is, the data type of the values to be stored.</p>
<p>In the example below, we are providing the data type <code>u32</code> in the first argument, and <code>u16</code> in the second argument of this function. This means that we are going to use <code>u32</code> values as keys in this hashtable, while <code>u16</code> values are the actual values that are going to be stored into this hashtable. At the end of this process, the <code>hash_table</code> object contains a <code>HashMap</code> object that uses the default settings and context.</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb9"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb9-1"><a href="#cb9-1" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> std = <span class="bu">@import</span>(<span class="st">"std"</span>);</span>
<span id="cb9-2"><a href="#cb9-2" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> AutoHashMap = std.hash_map.AutoHashMap;</span>
<span id="cb9-3"><a href="#cb9-3" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb9-4"><a href="#cb9-4" aria-hidden="true" tabindex="-1"></a><span class="kw">pub</span> <span class="kw">fn</span> main() !<span class="dt">void</span> <span class="op">{</span></span>
<span id="cb9-5"><a href="#cb9-5" aria-hidden="true" tabindex="-1"></a>    <span class="kw">var</span> gpa = std.heap.GeneralPurposeAllocator(.<span class="op">{}</span>)<span class="op">{}</span>;</span>
<span id="cb9-6"><a href="#cb9-6" aria-hidden="true" tabindex="-1"></a>    <span class="kw">const</span> allocator = gpa.allocator();</span>
<span id="cb9-7"><a href="#cb9-7" aria-hidden="true" tabindex="-1"></a>    <span class="kw">var</span> hash_table = AutoHashMap(<span class="dt">u32</span>, <span class="dt">u16</span>).init(allocator);</span>
<span id="cb9-8"><a href="#cb9-8" aria-hidden="true" tabindex="-1"></a>    <span class="kw">defer</span> hash_table.deinit();</span>
<span id="cb9-9"><a href="#cb9-9" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb9-10"><a href="#cb9-10" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> hash_table.put(<span class="dv">54321</span>, <span class="dv">89</span>);</span>
<span id="cb9-11"><a href="#cb9-11" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> hash_table.put(<span class="dv">50050</span>, <span class="dv">55</span>);</span>
<span id="cb9-12"><a href="#cb9-12" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> hash_table.put(<span class="dv">57709</span>, <span class="dv">41</span>);</span>
<span id="cb9-13"><a href="#cb9-13" aria-hidden="true" tabindex="-1"></a>    std.debug.print(</span>
<span id="cb9-14"><a href="#cb9-14" aria-hidden="true" tabindex="-1"></a>        <span class="st">"N of values stored: {d}</span><span class="sc">\n</span><span class="st">"</span>,</span>
<span id="cb9-15"><a href="#cb9-15" aria-hidden="true" tabindex="-1"></a>        .<span class="op">{</span>hash_table.count()<span class="op">}</span></span>
<span id="cb9-16"><a href="#cb9-16" aria-hidden="true" tabindex="-1"></a>    );</span>
<span id="cb9-17"><a href="#cb9-17" aria-hidden="true" tabindex="-1"></a>    std.debug.print(</span>
<span id="cb9-18"><a href="#cb9-18" aria-hidden="true" tabindex="-1"></a>        <span class="st">"Value at key 50050: {d}</span><span class="sc">\n</span><span class="st">"</span>,</span>
<span id="cb9-19"><a href="#cb9-19" aria-hidden="true" tabindex="-1"></a>        .<span class="op">{</span>hash_table.get(<span class="dv">50050</span>).?<span class="op">}</span></span>
<span id="cb9-20"><a href="#cb9-20" aria-hidden="true" tabindex="-1"></a>    );</span>
<span id="cb9-21"><a href="#cb9-21" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb9-22"><a href="#cb9-22" aria-hidden="true" tabindex="-1"></a>    <span class="kw">if</span> (hash_table.remove(<span class="dv">57709</span>)) <span class="op">{</span></span>
<span id="cb9-23"><a href="#cb9-23" aria-hidden="true" tabindex="-1"></a>        std.debug.print(</span>
<span id="cb9-24"><a href="#cb9-24" aria-hidden="true" tabindex="-1"></a>            <span class="st">"Value at key 57709 successfully removed!</span><span class="sc">\n</span><span class="st">"</span>,</span>
<span id="cb9-25"><a href="#cb9-25" aria-hidden="true" tabindex="-1"></a>            .<span class="op">{}</span></span>
<span id="cb9-26"><a href="#cb9-26" aria-hidden="true" tabindex="-1"></a>        );</span>
<span id="cb9-27"><a href="#cb9-27" aria-hidden="true" tabindex="-1"></a>    <span class="op">}</span></span>
<span id="cb9-28"><a href="#cb9-28" aria-hidden="true" tabindex="-1"></a>    std.debug.print(</span>
<span id="cb9-29"><a href="#cb9-29" aria-hidden="true" tabindex="-1"></a>        <span class="st">"N of values stored: {d}</span><span class="sc">\n</span><span class="st">"</span>,</span>
<span id="cb9-30"><a href="#cb9-30" aria-hidden="true" tabindex="-1"></a>        .<span class="op">{</span>hash_table.count()<span class="op">}</span></span>
<span id="cb9-31"><a href="#cb9-31" aria-hidden="true" tabindex="-1"></a>    );</span>
<span id="cb9-32"><a href="#cb9-32" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<pre><code>N of values stored: 3
Value at key 50050: 55
Value at key 57709 successfully removed!
N of values stored: 2</code></pre>
<p>You can add/put new values into the hashtable by using the <code>put()</code> method. The first argument is the key to be used, and the second argument is the actual value that you want to store inside the hashtable. In the example below, we first add the value 89 using the key 54321, next, we add the value 55 using the key 50050, etc.</p>
<p>Notice that we have used the method <code>count()</code> to see how many values are currently stored in the hashtable. After that, we also use the <code>get()</code> method to access (or look) at the value stored in the position identified by the key 500050. The output of this <code>get()</code> method is an optional value. This is why we use the <code>?</code> method at the end to get the actual value.</p>
<p>Also notice that we can remove (or delete) values from the hashtable by using the <code>remove()</code> method. You provide the key that identifies the value that you want to delete, then, the method will delete this value and return a <code>true</code> value as output. This <code>true</code> value essentially tells us that the method successfully deleted the value.</p>
<p>But this delete operation might not be always successful. For example, you might provide the wrong key to this method. I mean, maybe you provide (either intentionally or unintentionally) a key that points to an empty bucket, i.e., a bucket that still doesn’t have a value in it. In this case, the <code>remove()</code> method would return a <code>false</code> value.</p>
</section>
<section id="iterating-through-the-hashtable" class="level3" data-number="11.2.3">
<h3 data-number="11.2.3" class="anchored" data-anchor-id="iterating-through-the-hashtable"><span class="header-section-number">11.2.3</span> Iterating through the hashtable</h3>
<p>Iterating through the keys and values that are currently being stored in the hashtable is a very common necessity. You can do that in Zig by using an iterator object that can iterate through the elements of your hashtable object.</p>
<p>This iterator object works like any other iterator object that you would find in languages such as C++ and Rust. It’s basically a pointer object that points to some value in the container, and has a <code>next()</code> method that you can use to navigate (or iterate) through the values in the container.</p>
<p>You can create such iterator object by using the <code>iterator()</code> method of the hashtable object. This method returns an iterator object, from which you can use the <code>next()</code> method in conjunction with a while loop to iterate through the elements of your hashtable. The <code>next()</code> method returns an optional <code>Entry</code> value, and therefore, you must unwrap this optional value to get the actual <code>Entry</code> value from which you can access the key and also the value identified by this key.</p>
<p>With this <code>Entry</code> value at hand, you can access the key of this current entry by using the <code>key_ptr</code> attribute and dereferencing the pointer that lives inside of it, while the value identified by this key is accessed through the <code>value_ptr</code> attribute instead, which is also a pointer to be dereferenced. The code example below demonstrates the use of these elements:</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb11"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb11-1"><a href="#cb11-1" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> std = <span class="bu">@import</span>(<span class="st">"std"</span>);</span>
<span id="cb11-2"><a href="#cb11-2" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> AutoHashMap = std.hash_map.AutoHashMap;</span>
<span id="cb11-3"><a href="#cb11-3" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb11-4"><a href="#cb11-4" aria-hidden="true" tabindex="-1"></a><span class="kw">pub</span> <span class="kw">fn</span> main() !<span class="dt">void</span> <span class="op">{</span></span>
<span id="cb11-5"><a href="#cb11-5" aria-hidden="true" tabindex="-1"></a>    <span class="kw">var</span> gpa = std.heap.GeneralPurposeAllocator(.<span class="op">{}</span>)<span class="op">{}</span>;</span>
<span id="cb11-6"><a href="#cb11-6" aria-hidden="true" tabindex="-1"></a>    <span class="kw">const</span> allocator = gpa.allocator();</span>
<span id="cb11-7"><a href="#cb11-7" aria-hidden="true" tabindex="-1"></a>    <span class="kw">var</span> hash_table = AutoHashMap(<span class="dt">u32</span>, <span class="dt">u16</span>).init(allocator);</span>
<span id="cb11-8"><a href="#cb11-8" aria-hidden="true" tabindex="-1"></a>    <span class="kw">defer</span> hash_table.deinit();</span>
<span id="cb11-9"><a href="#cb11-9" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb11-10"><a href="#cb11-10" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> hash_table.put(<span class="dv">54321</span>, <span class="dv">89</span>);</span>
<span id="cb11-11"><a href="#cb11-11" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> hash_table.put(<span class="dv">50050</span>, <span class="dv">55</span>);</span>
<span id="cb11-12"><a href="#cb11-12" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> hash_table.put(<span class="dv">57709</span>, <span class="dv">41</span>);</span>
<span id="cb11-13"><a href="#cb11-13" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb11-14"><a href="#cb11-14" aria-hidden="true" tabindex="-1"></a>    <span class="kw">var</span> it = hash_table.iterator();</span>
<span id="cb11-15"><a href="#cb11-15" aria-hidden="true" tabindex="-1"></a>    <span class="kw">while</span> (it.next()) |kv| <span class="op">{</span></span>
<span id="cb11-16"><a href="#cb11-16" aria-hidden="true" tabindex="-1"></a>        <span class="co">// Access the current key</span></span>
<span id="cb11-17"><a href="#cb11-17" aria-hidden="true" tabindex="-1"></a>        std.debug.print(<span class="st">"Key: {d} | "</span>, .<span class="op">{</span>kv.key_ptr.*<span class="op">}</span>);</span>
<span id="cb11-18"><a href="#cb11-18" aria-hidden="true" tabindex="-1"></a>        <span class="co">// Access the current value</span></span>
<span id="cb11-19"><a href="#cb11-19" aria-hidden="true" tabindex="-1"></a>        std.debug.print(<span class="st">"Value: {d}</span><span class="sc">\n</span><span class="st">"</span>, .<span class="op">{</span>kv.value_ptr.*<span class="op">}</span>);</span>
<span id="cb11-20"><a href="#cb11-20" aria-hidden="true" tabindex="-1"></a>    <span class="op">}</span></span>
<span id="cb11-21"><a href="#cb11-21" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<pre><code>Key: 54321 | Value: 89
Key: 50050 | Value: 55
Key: 57709 | Value: 41</code></pre>
<p>If you want to iterate specifically through the values or the keys of your hashtable, you can create a key iterator or a value iterator object. These are also iterator objects, which have the same <code>next()</code> method that you can use to iterate through the hashtable.</p>
<p>Key iterators are created from the <code>keyIterator()</code> method of your hashtable object, while value iterators are created from the <code>valueIterator()</code> method. All you have to do is to unwrap the value from the <code>next()</code> method and deference it directly to access the key or the value that you are iterating over. The code example below demonstrates the use of a key iterator, but you can replicate the same logic to a value iterator.</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb13"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb13-1"><a href="#cb13-1" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> kit = hash_table.keyIterator();</span>
<span id="cb13-2"><a href="#cb13-2" aria-hidden="true" tabindex="-1"></a><span class="kw">while</span> (kit.next()) |key| <span class="op">{</span></span>
<span id="cb13-3"><a href="#cb13-3" aria-hidden="true" tabindex="-1"></a>    std.debug.print(<span class="st">"Key: {d}</span><span class="sc">\n</span><span class="st">"</span>, .<span class="op">{</span>key.*<span class="op">}</span>);</span>
<span id="cb13-4"><a href="#cb13-4" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<pre><code>Key: 54321
Key: 50050
Key: 57709</code></pre>
</section>
<section id="sec-array-map" class="level3" data-number="11.2.4">
<h3 data-number="11.2.4" class="anchored" data-anchor-id="sec-array-map"><span class="header-section-number">11.2.4</span> The <code>ArrayHashMap</code> hashtable</h3>
<p>If you need to iterate through the elements of your hashtable constantly, you might want to use the <code>ArrayHashMap</code> struct for your specific case, instead of going with the usual and general-purpose <code>HashMap</code> struct.</p>
<p>The <code>ArrayHashMap</code> struct creates a hashtable that is faster to iterate over. That is why this specific type of hashtable might be valuable to you. Some other properties of a <code>ArrayHashMap</code> hashtable are:</p>
<ul>
<li>the order of insertion is preserved, i.e., the order of the values that you find while iterating through this hashtable is actually the order in which these values were inserted in the hashtable.</li>
<li>the key-value pairs are stored sequentially, one after another.</li>
</ul>
<p>You can create an <code>ArrayHashMap</code> object by using, once again, a helper function that chooses automatically for you a hash function implementation. This is the <code>AutoArrayHashMap()</code> function, which works very similarly to the <code>AutoHashMap()</code> function that we presented in <a href="#sec-hashmap" class="quarto-xref"><span>Section 11.2.2</span></a>.</p>
<p>You provide two data types to this function. The data type of the keys that will be used in this hashtable, and the data type of the values that will be stored in this hashtable.</p>
<p>An <code>ArrayHashMap</code> object have essentially the exact same methods from the <code>HashMap</code> struct. So you can insert new values into the hashtable by using the <code>put()</code> method, and you can look (or get) a value from the hashtable by using the <code>get()</code> method. But the <code>remove()</code> method is not available in this specific type of hashtable.</p>
<p>In order to delete values from the hashtable, you would use the same methods that you find in an <code>ArrayList</code> object, i.e., a dynamic array. I presented these methods in <a href="#sec-dynamic-array-remove" class="quarto-xref"><span>Section 11.1.4</span></a>, which are the <code>swapRemove()</code> and <code>orderedRemove()</code> methods. These methods have the same meaning here, or, the same effect that they have in an <code>ArrayList</code> object.</p>
<p>This means that, with <code>swapRemove()</code> you remove the value from the hashtable, but you do not preserve the order in which the values were inserted into the structure. While <code>orderedRemove()</code> is able to retain the order in which these values were inserted.</p>
<p>But instead of providing an index as input to <code>swapRemove()</code> or <code>orderedRemove()</code>, like I described in <a href="#sec-dynamic-array-remove" class="quarto-xref"><span>Section 11.1.4</span></a>, these methods here in an <code>ArrayHashMap</code> take a key as input, like the <code>remove()</code> method from a <code>HashMap</code> object. If you want to provide an index as input, instead of a key, you should use the <code>swapRemoveAt()</code> and <code>orderedRemoveAt()</code> methods.</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb15"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb15-1"><a href="#cb15-1" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> hash_table = AutoArrayHashMap(<span class="dt">u32</span>, <span class="dt">u16</span>)</span>
<span id="cb15-2"><a href="#cb15-2" aria-hidden="true" tabindex="-1"></a>    .init(allocator);</span>
<span id="cb15-3"><a href="#cb15-3" aria-hidden="true" tabindex="-1"></a><span class="kw">defer</span> hash_table.deinit();</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
</section>
<section id="sec-string-hash-map" class="level3" data-number="11.2.5">
<h3 data-number="11.2.5" class="anchored" data-anchor-id="sec-string-hash-map"><span class="header-section-number">11.2.5</span> The <code>StringHashMap</code> hashtable</h3>
<p>One thing that you will notice in the other two types of hashtables that I have presented over the last sections, is that neither of them accepts a slice data type in their keys. What this means is that you cannot use a slice value to represent a key in these types of hashtable.</p>
<p>The most obvious consequence of this, is that you cannot use strings as keys in these hashtables. But it’s extremely common to use strings as keys in hashtables.</p>
<p>Take this very simple Javascript code snippet as an example. We are creating a simple hashtable object named <code>people</code>. Then, we add a new entry to this hashtable, which is identified by the string <code>'Pedro'</code>. This string is the key in this case, while the object containing different personal information such as age, height and city, is the value to be stored in the hashtable.</p>
<div class="sourceCode" id="cb16"><pre class="sourceCode js code-with-copy"><code class="sourceCode javascript"><span id="cb16-1"><a href="#cb16-1" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> people <span class="op">=</span> <span class="kw">new</span> <span class="bu">Object</span>()<span class="op">;</span></span>
<span id="cb16-2"><a href="#cb16-2" aria-hidden="true" tabindex="-1"></a>people[<span class="st">'Pedro'</span>] <span class="op">=</span> {</span>
<span id="cb16-3"><a href="#cb16-3" aria-hidden="true" tabindex="-1"></a>    <span class="st">'age'</span><span class="op">:</span> <span class="dv">25</span><span class="op">,</span></span>
<span id="cb16-4"><a href="#cb16-4" aria-hidden="true" tabindex="-1"></a>    <span class="st">'height'</span><span class="op">:</span> <span class="fl">1.67</span><span class="op">,</span></span>
<span id="cb16-5"><a href="#cb16-5" aria-hidden="true" tabindex="-1"></a>    <span class="st">'city'</span><span class="op">:</span> <span class="st">'Belo Horizonte'</span></span>
<span id="cb16-6"><a href="#cb16-6" aria-hidden="true" tabindex="-1"></a>}<span class="op">;</span></span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
<p>This pattern of using strings as keys is very common in all sorts of situations. That is why the Zig Standard Library offers a specific type of hashtable for this purpose, which is created through the <code>StringHashMap()</code> function. This function creates a hashtable that uses strings as keys. The only input of this function is the data type of the values that will be stored into this hashtable.</p>
<p>In the example below, I’m creating a hashtable to store the ages of different people. Each key in this hashtable is represented by the name of each person, while the value stored in the hashtable is the age of this person identified by the key.</p>
<p>That is why I provide the <code>u8</code> data type (which is the data type used by the age values) as input to this <code>StringHashMap()</code> function. As the result, it creates a hashtable that uses string values as keys, and, that stores <code>u8</code> values in it. Notice that an allocator object is provided at the <code>init()</code> method of the resulting object from the <code>StringHashMap()</code> function.</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb17"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb17-1"><a href="#cb17-1" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> std = <span class="bu">@import</span>(<span class="st">"std"</span>);</span>
<span id="cb17-2"><a href="#cb17-2" aria-hidden="true" tabindex="-1"></a><span class="kw">pub</span> <span class="kw">fn</span> main() !<span class="dt">void</span> <span class="op">{</span></span>
<span id="cb17-3"><a href="#cb17-3" aria-hidden="true" tabindex="-1"></a>    <span class="kw">var</span> gpa = std.heap.GeneralPurposeAllocator(.<span class="op">{}</span>)<span class="op">{}</span>;</span>
<span id="cb17-4"><a href="#cb17-4" aria-hidden="true" tabindex="-1"></a>    <span class="kw">const</span> allocator = gpa.allocator();</span>
<span id="cb17-5"><a href="#cb17-5" aria-hidden="true" tabindex="-1"></a>    <span class="kw">var</span> ages = std.StringHashMap(<span class="dt">u8</span>).init(allocator);</span>
<span id="cb17-6"><a href="#cb17-6" aria-hidden="true" tabindex="-1"></a>    <span class="kw">defer</span> ages.deinit();</span>
<span id="cb17-7"><a href="#cb17-7" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb17-8"><a href="#cb17-8" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> ages.put(<span class="st">"Pedro"</span>, <span class="dv">25</span>);</span>
<span id="cb17-9"><a href="#cb17-9" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> ages.put(<span class="st">"Matheus"</span>, <span class="dv">21</span>);</span>
<span id="cb17-10"><a href="#cb17-10" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> ages.put(<span class="st">"Abgail"</span>, <span class="dv">42</span>);</span>
<span id="cb17-11"><a href="#cb17-11" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb17-12"><a href="#cb17-12" aria-hidden="true" tabindex="-1"></a>    <span class="kw">var</span> it = ages.iterator();</span>
<span id="cb17-13"><a href="#cb17-13" aria-hidden="true" tabindex="-1"></a>    <span class="kw">while</span> (it.next()) |kv| <span class="op">{</span></span>
<span id="cb17-14"><a href="#cb17-14" aria-hidden="true" tabindex="-1"></a>        std.debug.print(<span class="st">"Key: {s} | "</span>, .<span class="op">{</span>kv.key_ptr.*<span class="op">}</span>);</span>
<span id="cb17-15"><a href="#cb17-15" aria-hidden="true" tabindex="-1"></a>        std.debug.print(<span class="st">"Age: {d}</span><span class="sc">\n</span><span class="st">"</span>, .<span class="op">{</span>kv.value_ptr.*<span class="op">}</span>);</span>
<span id="cb17-16"><a href="#cb17-16" aria-hidden="true" tabindex="-1"></a>    <span class="op">}</span></span>
<span id="cb17-17"><a href="#cb17-17" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<pre><code>Key: Pedro | Age: 25
Key: Abgail | Age: 42
Key: Matheus | Age: 21</code></pre>
</section>
<section id="the-stringarrayhashmap-hashtable" class="level3" data-number="11.2.6">
<h3 data-number="11.2.6" class="anchored" data-anchor-id="the-stringarrayhashmap-hashtable"><span class="header-section-number">11.2.6</span> The <code>StringArrayHashMap</code> hashtable</h3>
<p>The Zig Standard Library also provides a type of hashtable that mix the cons and pros of the <code>StringHashMap</code> and <code>ArrayHashMap</code> together. That is, a hashtable that uses strings as keys, but also have the advantages from <code>ArrayHashMap</code>. In other words, you can have a hashtable that is fast to iterate over, that preserves insertion order, and also, that uses strings as keys.</p>
<p>You can create such type of hashtable by using the <code>StringArrayHashMap()</code> function. This function accepts a data type as input, which is the data type of the values that are going to be stored inside this hashtable, in the same style as the function presented in <a href="#sec-string-hash-map" class="quarto-xref"><span>Section 11.2.5</span></a>.</p>
<p>You can insert new values into this hashtable by using the same <code>put()</code> method that we have discussed in <a href="#sec-string-hash-map" class="quarto-xref"><span>Section 11.2.5</span></a>. And you can also get values from the hashtable by using the same <code>get()</code> method. Like its <code>ArrayHashMap</code> brother, to delete values from this specific type of hashtable, we also use the <code>orderedRemove()</code> and <code>swapRemove()</code> methods, with the same effects that I have described in <a href="#sec-array-map" class="quarto-xref"><span>Section 11.2.4</span></a>.</p>
<p>If we take the code example that was exposed in <a href="#sec-string-hash-map" class="quarto-xref"><span>Section 11.2.5</span></a>, we can achieve the exact same result with <code>StringArrayHashMap()</code>:</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb19"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb19-1"><a href="#cb19-1" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> ages = std.StringArrayHashMap(<span class="dt">u8</span>).init(allocator);</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
</section>
</section>
<section id="linked-lists" class="level2" data-number="11.3">
<h2 data-number="11.3" class="anchored" data-anchor-id="linked-lists"><span class="header-section-number">11.3</span> Linked lists</h2>
<p>The Zig Standard Library provides an implementation for both singly and doubly linked lists. More specifically, through the structs <code>SinglyLinkedList</code> and <code>DoublyLinkedList</code>.</p>
<p>In case you are not familiar with these data structures, a linked list is a linear data structure that looks like a chain, or, a rope. The main advantage of this data structure is that you normally have very fast insertion and deletion operations. But, as a disadvantage, iterating through this data structure is usually not so fast as iterating through an array.</p>
<p>The idea behind a linked list is to build a structure that consists of a sequence of nodes connected to each other by pointers. This means that linked lists are usually not contiguous in memory, because each node might be anywhere in memory. They do not need to be close to one another.</p>
<p>In <a href="#fig-linked-list" class="quarto-xref">Figure&nbsp;<span>11.3</span></a> we can see a diagram of a singly linked list. We begin at the first node (which is usually called “the head of the linked list”). Then, from this first node we uncover the remaining nodes in the structure, by following the locations pointed by the pointers found in each node.</p>
<p>Each node has two things in it. It has the value that is stored in the current node , and also, a pointer. This pointer points to the next node in the list. If this pointer is null, then, it means that we have reached the end of our linked list.</p>
<div id="fig-linked-list" class="quarto-float quarto-figure quarto-figure-center anchored">
<figure class="quarto-float quarto-float-fig figure">
<div aria-describedby="fig-linked-list-caption-0ceaefa1-69ba-4598-a22c-09a6ac19f8ca">
<img src="./../Figures/linked-list.png" class="img-fluid figure-img">
</div>
<figcaption class="quarto-float-caption-bottom quarto-float-caption quarto-float-fig" id="fig-linked-list-caption-0ceaefa1-69ba-4598-a22c-09a6ac19f8ca">
Figure&nbsp;11.3: A diagram of a singly linked list.
</figcaption>
</figure>
</div>
<p>In <a href="#fig-linked-list2" class="quarto-xref">Figure&nbsp;<span>11.4</span></a> we can see a diagram of a doubly linked list. The only thing that really changes now is that every node in the linked list has both a pointer to the previous node, and, a pointer to the next node. So every node in a doubly linked list has two pointers in it. These are usually called the <code>prev</code> (for “previous”) and the <code>next</code> (for “next”) pointers of the node.</p>
<p>In the singly linked list example, we had only one single pointer in each node, and this singular pointer was always pointing to the next node in the sequence. This means that singly linked lists normally have only the <code>next</code> pointer in them.</p>
<div id="fig-linked-list2" class="quarto-float quarto-figure quarto-figure-center anchored">
<figure class="quarto-float quarto-float-fig figure">
<div aria-describedby="fig-linked-list2-caption-0ceaefa1-69ba-4598-a22c-09a6ac19f8ca">
<img src="./../Figures/doubly-linked-list.png" class="img-fluid figure-img">
</div>
<figcaption class="quarto-float-caption-bottom quarto-float-caption quarto-float-fig" id="fig-linked-list2-caption-0ceaefa1-69ba-4598-a22c-09a6ac19f8ca">
Figure&nbsp;11.4: A diagram of a doubly linked list.
</figcaption>
</figure>
</div>
<section id="recent-change-in-the-api" class="level3" data-number="11.3.1">
<h3 data-number="11.3.1" class="anchored" data-anchor-id="recent-change-in-the-api"><span class="header-section-number">11.3.1</span> Recent change in the API</h3>
<p>On previous versions of Zig, the <code>SinglyLinkedList</code> and <code>DoublyLinkedList</code> structs were initially implemented as “generics data structures”. Meaning that, you would use a generic function to create a singly (or doubly) linked list that could store the specific data type that you wanted to use. We will learn more about generics at <a href="10-stack-project.html#sec-generics" class="quarto-xref"><span>Section 12.2</span></a>, and also, how we can create a “generic data structure” at <a href="10-stack-project.html#sec-generic-struct" class="quarto-xref"><span>Section 12.2.2</span></a>.</p>
<p>However, on the latest versions of Zig, the structs <code>SinglyLinkedList</code> and <code>DoublyLinkedList</code> were altered to use a “less generic API”. This specific change was introduced on April 3, 2025. Therefore, check if your Zig version is one released after this date. Just have in mind that if you don’t have a very recent version of the Zig compiler, you might have problems while trying to compile the next examples exposed here.</p>
</section>
<section id="how-to-use-a-singly-linked-list" class="level3" data-number="11.3.2">
<h3 data-number="11.3.2" class="anchored" data-anchor-id="how-to-use-a-singly-linked-list"><span class="header-section-number">11.3.2</span> How to use a singly linked list</h3>
<p>For example, consider that you are creating a singly linked list that is going to store <code>u32</code> values. Given this scenario, the first thing that we need to do, is to create a “node type” that is capable of storing a <code>u32</code> value. The <code>NodeU32</code> type exposed below demonstrates such “node type”.</p>
<p>Notice that the data type associated with the member named <code>data</code> is the most important part of this custom “node type”. It determines the data type that is going to be stored in each node.</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb20"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb20-1"><a href="#cb20-1" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> std = <span class="bu">@import</span>(<span class="st">"std"</span>);</span>
<span id="cb20-2"><a href="#cb20-2" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> NodeU32 = <span class="kw">struct</span> <span class="op">{</span></span>
<span id="cb20-3"><a href="#cb20-3" aria-hidden="true" tabindex="-1"></a>    data: <span class="dt">u32</span>,</span>
<span id="cb20-4"><a href="#cb20-4" aria-hidden="true" tabindex="-1"></a>    node: std.SinglyLinkedList.Node = .<span class="op">{}</span>,</span>
<span id="cb20-5"><a href="#cb20-5" aria-hidden="true" tabindex="-1"></a><span class="op">}</span>;</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<p>After we created our custom “node type” that can store the specific data type that we want, we can just create a new and empty singly linked list, which will store our nodes. To do that, we just create a new object with the type <code>SinglyLinkedList</code>, like this:</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb21"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb21-1"><a href="#cb21-1" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> list: std.SinglyLinkedList = .<span class="op">{}</span>;</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<p>Now, we have our linked list… But how can we insert nodes in it? Well, first of all, we need to create our nodes. So let’s focus on that first. The snippet exposed below demonstrates how we could use our <code>NodeU32</code> struct to create such nodes.</p>
<p>Notice in this snippet that we are just setting the <code>data</code> member of the struct for now. We don’t need to connect these nodes together in this first instance. This is why we ignore the <code>node</code> member at first. But we are going to connect these nodes in a future point of the code, which is why these objects are marked as “variable objects”, so that we can alter them in the future.</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb22"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb22-1"><a href="#cb22-1" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> one: NodeU32 = .<span class="op">{</span> .data = <span class="dv">1</span> <span class="op">}</span>;</span>
<span id="cb22-2"><a href="#cb22-2" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> two: NodeU32 = .<span class="op">{</span> .data = <span class="dv">2</span> <span class="op">}</span>;</span>
<span id="cb22-3"><a href="#cb22-3" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> three: NodeU32 = .<span class="op">{</span> .data = <span class="dv">3</span> <span class="op">}</span>;</span>
<span id="cb22-4"><a href="#cb22-4" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> five: NodeU32 = .<span class="op">{</span> .data = <span class="dv">5</span> <span class="op">}</span>;</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<p>Now that we have both the linked list and also the nodes created, we can start to connect them together. You can use the <code>prepend()</code> method from the linked list object to insert the first node in the list, which is the “head” of the linked list. As the name suggests, this specific method prepends the input node to the linked list, or, in other words, it transforms the input node into the first node of the list.</p>
<p>After we added the “head node” of the list, we can start to add the “next nodes” in the list by using the <code>insertAfter()</code> method from the <code>SinglyLinkedList.Node</code> type, which, in our case here, is accessible through the <code>node</code> member of our <code>NodeU32</code> type. Thus, we can start to create the connections between the nodes by calling this method from the node objects that are present in the list. Like in this example below:</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb23"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb23-1"><a href="#cb23-1" aria-hidden="true" tabindex="-1"></a>list.prepend(&amp;two.node); <span class="co">// {2}</span></span>
<span id="cb23-2"><a href="#cb23-2" aria-hidden="true" tabindex="-1"></a>two.node.insertAfter(&amp;five.node); <span class="co">// {2, 5}</span></span>
<span id="cb23-3"><a href="#cb23-3" aria-hidden="true" tabindex="-1"></a>two.node.insertAfter(&amp;three.node); <span class="co">// {2, 3, 5}</span></span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<p>You can also call the <code>prepend()</code> method again to add new nodes to the beginning of the linked list, which means, effectively, changing the “head node” of the list, like this:</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb24"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb24-1"><a href="#cb24-1" aria-hidden="true" tabindex="-1"></a>list.prepend(&amp;one.node); <span class="co">// {1, 2, 3, 5}</span></span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<p>There are other methods available from the singly linked list object that you might be interested. You can find a summary of them in the bullet points below:</p>
<ul>
<li><code>remove()</code> to remove a specific node from the linked list.</li>
<li><code>len()</code> to count how many nodes there is in the linked list.</li>
<li><code>popFirst()</code> to remove the first node (i.e., the “head”) from the linked list.</li>
</ul>
<p>So, that is how singly linked lists work in Zig in a nutshell. To sum up, this is all the source code that was exposed in this section inside the single cell:</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb25"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb25-1"><a href="#cb25-1" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> NodeU32 = <span class="kw">struct</span> <span class="op">{</span></span>
<span id="cb25-2"><a href="#cb25-2" aria-hidden="true" tabindex="-1"></a>    data: <span class="dt">u32</span>,</span>
<span id="cb25-3"><a href="#cb25-3" aria-hidden="true" tabindex="-1"></a>    node: std.SinglyLinkedList.Node = .<span class="op">{}</span>,</span>
<span id="cb25-4"><a href="#cb25-4" aria-hidden="true" tabindex="-1"></a><span class="op">}</span>;</span>
<span id="cb25-5"><a href="#cb25-5" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb25-6"><a href="#cb25-6" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> list: std.SinglyLinkedList = .<span class="op">{}</span>;</span>
<span id="cb25-7"><a href="#cb25-7" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> one: NodeU32 = .<span class="op">{</span> .data = <span class="dv">1</span> <span class="op">}</span>;</span>
<span id="cb25-8"><a href="#cb25-8" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> two: NodeU32 = .<span class="op">{</span> .data = <span class="dv">2</span> <span class="op">}</span>;</span>
<span id="cb25-9"><a href="#cb25-9" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> three: NodeU32 = .<span class="op">{</span> .data = <span class="dv">3</span> <span class="op">}</span>;</span>
<span id="cb25-10"><a href="#cb25-10" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> five: NodeU32 = .<span class="op">{</span> .data = <span class="dv">5</span> <span class="op">}</span>;</span>
<span id="cb25-11"><a href="#cb25-11" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb25-12"><a href="#cb25-12" aria-hidden="true" tabindex="-1"></a>list.prepend(&amp;two.node); <span class="co">// {2}</span></span>
<span id="cb25-13"><a href="#cb25-13" aria-hidden="true" tabindex="-1"></a>two.node.insertAfter(&amp;five.node); <span class="co">// {2, 5}</span></span>
<span id="cb25-14"><a href="#cb25-14" aria-hidden="true" tabindex="-1"></a>two.node.insertAfter(&amp;three.node); <span class="co">// {2, 3, 5}</span></span>
<span id="cb25-15"><a href="#cb25-15" aria-hidden="true" tabindex="-1"></a>list.prepend(&amp;one.node); <span class="co">// {1, 2, 3, 5}</span></span>
<span id="cb25-16"><a href="#cb25-16" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb25-17"><a href="#cb25-17" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> stdout.print(<span class="st">"Number of nodes: {}"</span>, .<span class="op">{</span>list.len()<span class="op">}</span>);</span>
<span id="cb25-18"><a href="#cb25-18" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> stdout.flush();</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
<div class="cell-output cell-output-stdout">
<pre><code>Number of nodes: 4</code></pre>
</div>
</div>
</section>
<section id="how-to-use-a-doubly-linked-list" class="level3" data-number="11.3.3">
<h3 data-number="11.3.3" class="anchored" data-anchor-id="how-to-use-a-doubly-linked-list"><span class="header-section-number">11.3.3</span> How to use a doubly linked list</h3>
<p>If you want to use a doubly linked list instead, you will face a similar workflow compared to the singly linked list:</p>
<ol type="1">
<li>You first create a “custom node type” that can store the specific data type that you want.</li>
<li>Create an empty doubly linked list object.</li>
<li>Create the nodes of linked list.</li>
<li>Start to insert the nodes inside the list.</li>
</ol>
<p>In your “custom node type”, you should use the <code>DoublyLinkedList.Node</code> type to denote the <code>node</code> member of the struct. The snippet below demonstrates that. Here we are creating, once again, a node type that can store <code>u32</code> values. But this time, this struct is tailored to be used inside a <code>DoublyLinkedList</code> struct.</p>
<p>After this step, the way that you create the new empty linked list, and the nodes that you want insert, is practically identical to the singly linked list case. But, this time, we normally use the <code>append()</code> method from the linked list object to add new nodes to the list.</p>
<p>This <code>append()</code> method from the linked list object will always append the input node to the end of the linked list. However, in case you want to add the new node into a different position of the list, then, you should take a look at the <code>insertAfter()</code> and <code>insertBefore()</code> methods of the linked list object. These methods allow you to insert the new node either after or before an existing node in the list.</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb27"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb27-1"><a href="#cb27-1" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> NodeU32 = <span class="kw">struct</span> <span class="op">{</span></span>
<span id="cb27-2"><a href="#cb27-2" aria-hidden="true" tabindex="-1"></a>    data: <span class="dt">u32</span>,</span>
<span id="cb27-3"><a href="#cb27-3" aria-hidden="true" tabindex="-1"></a>    node: std.DoublyLinkedList.Node = .<span class="op">{}</span>,</span>
<span id="cb27-4"><a href="#cb27-4" aria-hidden="true" tabindex="-1"></a><span class="op">}</span>;</span>
<span id="cb27-5"><a href="#cb27-5" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb27-6"><a href="#cb27-6" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> list: std.DoublyLinkedList = .<span class="op">{}</span>;</span>
<span id="cb27-7"><a href="#cb27-7" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> one: NodeU32 = .<span class="op">{</span> .data = <span class="dv">1</span> <span class="op">}</span>;</span>
<span id="cb27-8"><a href="#cb27-8" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> two: NodeU32 = .<span class="op">{</span> .data = <span class="dv">2</span> <span class="op">}</span>;</span>
<span id="cb27-9"><a href="#cb27-9" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> three: NodeU32 = .<span class="op">{</span> .data = <span class="dv">3</span> <span class="op">}</span>;</span>
<span id="cb27-10"><a href="#cb27-10" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> five: NodeU32 = .<span class="op">{</span> .data = <span class="dv">5</span> <span class="op">}</span>;</span>
<span id="cb27-11"><a href="#cb27-11" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb27-12"><a href="#cb27-12" aria-hidden="true" tabindex="-1"></a>list.append(&amp;one.node); <span class="co">// {1}</span></span>
<span id="cb27-13"><a href="#cb27-13" aria-hidden="true" tabindex="-1"></a>list.append(&amp;three.node); <span class="co">// {1, 3}</span></span>
<span id="cb27-14"><a href="#cb27-14" aria-hidden="true" tabindex="-1"></a>list.insertAfter(</span>
<span id="cb27-15"><a href="#cb27-15" aria-hidden="true" tabindex="-1"></a>    &amp;one.node,</span>
<span id="cb27-16"><a href="#cb27-16" aria-hidden="true" tabindex="-1"></a>    &amp;five.node</span>
<span id="cb27-17"><a href="#cb27-17" aria-hidden="true" tabindex="-1"></a>); <span class="co">// {1, 5, 3}</span></span>
<span id="cb27-18"><a href="#cb27-18" aria-hidden="true" tabindex="-1"></a>list.append(&amp;two.node); <span class="co">// {1, 5, 3, 2}</span></span>
<span id="cb27-19"><a href="#cb27-19" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb27-20"><a href="#cb27-20" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> stdout.print(<span class="st">"Number of nodes: {}"</span>, .<span class="op">{</span>list.len()<span class="op">}</span>);</span>
<span id="cb27-21"><a href="#cb27-21" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> stdout.flush();</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
<div class="cell-output cell-output-stdout">
<pre><code>Number of nodes: 4</code></pre>
</div>
</div>
<p>These are other methods from the <code>DoublyLinkedList</code> object that might interest you:</p>
<ul>
<li><code>remove()</code>: to remove a specific node from the list.</li>
<li><code>len()</code>: to count the number of nodes in the list.</li>
<li><code>prepend()</code>: to add a node to the beginning of the list (i.e.&nbsp;set the head node of the list).</li>
<li><code>pop()</code>: to remove the last node of the list.</li>
<li><code>popFirst()</code>: to remove the first node of the list.</li>
<li><code>concatByMoving()</code>: to concat two doubly linked lists together.</li>
</ul>
</section>
<section id="iterating-through-the-linked-list" class="level3" data-number="11.3.4">
<h3 data-number="11.3.4" class="anchored" data-anchor-id="iterating-through-the-linked-list"><span class="header-section-number">11.3.4</span> Iterating through the linked list</h3>
<p>If you want to iterate over the elements of the linked list, all you need to do is to follow the trail created by the “pointer to next node”. We usually do that inside a while loop, that simply goes to the next node over and over, until it finds a null pointer, which means that we hit the end of the list.</p>
<p>This next example demonstrates how such while loop would work. Notice that we are using the <code>@fieldParentPtr()</code> built-in function to get access to a pointer that points to the parent instance of the <code>node</code> object. In other words, we get access to a pointer to the <code>NodeU32</code> instance that contains the current node. This way, we can use this pointer to access the data that is currently stored in this node.</p>
<p>Also notice that in each iteration of the while loop, we are changing the value of the <code>it</code> variable to the next node in the list. The while loop is interrupted in the moment that this <code>it</code> variable becomes null, which will happen when the there is not “next node” in the list, which means that we have reached the end of the list.</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb29"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb29-1"><a href="#cb29-1" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> NodeU32 = <span class="kw">struct</span> <span class="op">{</span></span>
<span id="cb29-2"><a href="#cb29-2" aria-hidden="true" tabindex="-1"></a>    data: <span class="dt">u32</span>,</span>
<span id="cb29-3"><a href="#cb29-3" aria-hidden="true" tabindex="-1"></a>    node: std.SinglyLinkedList.Node = .<span class="op">{}</span>,</span>
<span id="cb29-4"><a href="#cb29-4" aria-hidden="true" tabindex="-1"></a><span class="op">}</span>;</span>
<span id="cb29-5"><a href="#cb29-5" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb29-6"><a href="#cb29-6" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> list: std.SinglyLinkedList = .<span class="op">{}</span>;</span>
<span id="cb29-7"><a href="#cb29-7" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> one: NodeU32 = .<span class="op">{</span> .data = <span class="dv">1</span> <span class="op">}</span>;</span>
<span id="cb29-8"><a href="#cb29-8" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> two: NodeU32 = .<span class="op">{</span> .data = <span class="dv">2</span> <span class="op">}</span>;</span>
<span id="cb29-9"><a href="#cb29-9" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> three: NodeU32 = .<span class="op">{</span> .data = <span class="dv">3</span> <span class="op">}</span>;</span>
<span id="cb29-10"><a href="#cb29-10" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> five: NodeU32 = .<span class="op">{</span> .data = <span class="dv">5</span> <span class="op">}</span>;</span>
<span id="cb29-11"><a href="#cb29-11" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb29-12"><a href="#cb29-12" aria-hidden="true" tabindex="-1"></a>list.prepend(&amp;two.node); <span class="co">// {2}</span></span>
<span id="cb29-13"><a href="#cb29-13" aria-hidden="true" tabindex="-1"></a>list.prepend(&amp;five.node); <span class="co">// {5, 2}</span></span>
<span id="cb29-14"><a href="#cb29-14" aria-hidden="true" tabindex="-1"></a>list.prepend(&amp;three.node); <span class="co">// {3, 5, 2}</span></span>
<span id="cb29-15"><a href="#cb29-15" aria-hidden="true" tabindex="-1"></a>list.prepend(&amp;one.node); <span class="co">// {1, 3, 5, 2}</span></span>
<span id="cb29-16"><a href="#cb29-16" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb29-17"><a href="#cb29-17" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> it = list.first;</span>
<span id="cb29-18"><a href="#cb29-18" aria-hidden="true" tabindex="-1"></a><span class="kw">while</span> (it) |node| : (it = node.next) <span class="op">{</span></span>
<span id="cb29-19"><a href="#cb29-19" aria-hidden="true" tabindex="-1"></a>    <span class="kw">const</span> l: *NodeU32 = <span class="bu">@fieldParentPtr</span>(</span>
<span id="cb29-20"><a href="#cb29-20" aria-hidden="true" tabindex="-1"></a>        <span class="st">"node"</span>, node</span>
<span id="cb29-21"><a href="#cb29-21" aria-hidden="true" tabindex="-1"></a>    );</span>
<span id="cb29-22"><a href="#cb29-22" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> stdout.print(</span>
<span id="cb29-23"><a href="#cb29-23" aria-hidden="true" tabindex="-1"></a>        <span class="st">"Current value: {}"</span>, .<span class="op">{</span>l.data<span class="op">}</span></span>
<span id="cb29-24"><a href="#cb29-24" aria-hidden="true" tabindex="-1"></a>    );</span>
<span id="cb29-25"><a href="#cb29-25" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb29-26"><a href="#cb29-26" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> stdout.flush();</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<pre><code>Current value: 1
Current value: 3
Current value: 5
Current value: 2</code></pre>
</section>
</section>
<section id="multi-array-structure" class="level2" data-number="11.4">
<h2 data-number="11.4" class="anchored" data-anchor-id="multi-array-structure"><span class="header-section-number">11.4</span> Multi array structure</h2>
<p>Zig introduces a new data structure called <code>MultiArrayList()</code>. It’s a different version of the dynamic array that we have introduced in <a href="#sec-dynamic-array" class="quarto-xref"><span>Section 11.1</span></a>. The difference between this structure and the <code>ArrayList()</code> that we know from <a href="#sec-dynamic-array" class="quarto-xref"><span>Section 11.1</span></a>, is that <code>MultiArrayList()</code> creates a separate dynamic array for each field of the struct that you provide as input.</p>
<p>Consider the following code example. We create a new custom struct called <code>Person</code>. This struct contains three different data members, or, three different fields. As consequence, when we provide this <code>Person</code> data type as input to <code>MultiArrayList()</code>, this creates a “struct of three different arrays” called <code>PersonArray</code>. In other words, this <code>PersonArray</code> is a struct that contains three internal dynamic arrays in it. One array for each field found in the <code>Person</code> struct definition.</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb31"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb31-1"><a href="#cb31-1" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> std = <span class="bu">@import</span>(<span class="st">"std"</span>);</span>
<span id="cb31-2"><a href="#cb31-2" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> Person = <span class="kw">struct</span> <span class="op">{</span></span>
<span id="cb31-3"><a href="#cb31-3" aria-hidden="true" tabindex="-1"></a>    name: []<span class="kw">const</span> <span class="dt">u8</span>,</span>
<span id="cb31-4"><a href="#cb31-4" aria-hidden="true" tabindex="-1"></a>    age: <span class="dt">u8</span>,</span>
<span id="cb31-5"><a href="#cb31-5" aria-hidden="true" tabindex="-1"></a>    height: <span class="dt">f32</span>,</span>
<span id="cb31-6"><a href="#cb31-6" aria-hidden="true" tabindex="-1"></a><span class="op">}</span>;</span>
<span id="cb31-7"><a href="#cb31-7" aria-hidden="true" tabindex="-1"></a><span class="kw">const</span> PersonArray = std.MultiArrayList(Person);</span>
<span id="cb31-8"><a href="#cb31-8" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb31-9"><a href="#cb31-9" aria-hidden="true" tabindex="-1"></a><span class="kw">pub</span> <span class="kw">fn</span> main() !<span class="dt">void</span> <span class="op">{</span></span>
<span id="cb31-10"><a href="#cb31-10" aria-hidden="true" tabindex="-1"></a>    <span class="kw">var</span> gpa = std.heap.GeneralPurposeAllocator(.<span class="op">{}</span>)<span class="op">{}</span>;</span>
<span id="cb31-11"><a href="#cb31-11" aria-hidden="true" tabindex="-1"></a>    <span class="kw">const</span> allocator = gpa.allocator();</span>
<span id="cb31-12"><a href="#cb31-12" aria-hidden="true" tabindex="-1"></a>    <span class="kw">var</span> people = PersonArray<span class="op">{}</span>;</span>
<span id="cb31-13"><a href="#cb31-13" aria-hidden="true" tabindex="-1"></a>    <span class="kw">defer</span> people.deinit(allocator);</span>
<span id="cb31-14"><a href="#cb31-14" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb31-15"><a href="#cb31-15" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> people.append(allocator, .<span class="op">{</span></span>
<span id="cb31-16"><a href="#cb31-16" aria-hidden="true" tabindex="-1"></a>        .name = <span class="st">"Auguste"</span>, .age = <span class="dv">15</span>, .height = <span class="fl">1.54</span></span>
<span id="cb31-17"><a href="#cb31-17" aria-hidden="true" tabindex="-1"></a>    <span class="op">}</span>);</span>
<span id="cb31-18"><a href="#cb31-18" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> people.append(allocator, .<span class="op">{</span></span>
<span id="cb31-19"><a href="#cb31-19" aria-hidden="true" tabindex="-1"></a>        .name = <span class="st">"Elena"</span>, .age = <span class="dv">26</span>, .height = <span class="fl">1.65</span></span>
<span id="cb31-20"><a href="#cb31-20" aria-hidden="true" tabindex="-1"></a>    <span class="op">}</span>);</span>
<span id="cb31-21"><a href="#cb31-21" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> people.append(allocator, .<span class="op">{</span></span>
<span id="cb31-22"><a href="#cb31-22" aria-hidden="true" tabindex="-1"></a>        .name = <span class="st">"Michael"</span>, .age = <span class="dv">64</span>, .height = <span class="fl">1.87</span></span>
<span id="cb31-23"><a href="#cb31-23" aria-hidden="true" tabindex="-1"></a>    <span class="op">}</span>);</span>
<span id="cb31-24"><a href="#cb31-24" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<p>In other words, instead of creating an array of “persons”, the <code>MultiArrayList()</code> function creates a “struct of arrays”. Each data member of this struct is a different array that stores the values of a specific field from the <code>Person</code> values that were added (or, appended) to this “struct of arrays”. One important detail is that each of these separate internal arrays stored inside <code>PersonArray</code> are dynamic arrays. This means that these arrays can grow in capacity automatically as needed, to accomodate more values.</p>
<p>The <a href="#fig-multi-array" class="quarto-xref">Figure&nbsp;<span>11.5</span></a> exposed below presents a diagram that describes the <code>PersonArray</code> struct that we have created in the previous code example. Notice that the values of the data members present in each of the three <code>Person</code> values that we have appended into the <code>PersonArray</code> object , are scattered across three different internal arrays of the <code>PersonArray</code> object.</p>
<div id="fig-multi-array" class="quarto-float quarto-figure quarto-figure-center anchored">
<figure class="quarto-float quarto-float-fig figure">
<div aria-describedby="fig-multi-array-caption-0ceaefa1-69ba-4598-a22c-09a6ac19f8ca">
<img src="./../Figures/multi-array.png" class="img-fluid figure-img">
</div>
<figcaption class="quarto-float-caption-bottom quarto-float-caption quarto-float-fig" id="fig-multi-array-caption-0ceaefa1-69ba-4598-a22c-09a6ac19f8ca">
Figure&nbsp;11.5: A diagram of the <code>PersonArray</code> struct.
</figcaption>
</figure>
</div>
<p>You can easily access each of these arrays separately, and iterate over the values of each array. For that, you will need to call the <code>items()</code> method from the <code>PersonArray</code> object, and provide as input to this method, the name of the field that you want to iterate over. If you want to iterate through the <code>.age</code> array for example, then, you need to call <code>items(.age)</code> from the <code>PersonArray</code> object, like in the example below:</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb32"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb32-1"><a href="#cb32-1" aria-hidden="true" tabindex="-1"></a><span class="kw">for</span> (people.items(.age)) |*age| <span class="op">{</span></span>
<span id="cb32-2"><a href="#cb32-2" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> stdout.print(<span class="st">"Age: {d}</span><span class="sc">\n</span><span class="st">"</span>, .<span class="op">{</span>age.*<span class="op">}</span>);</span>
<span id="cb32-3"><a href="#cb32-3" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb32-4"><a href="#cb32-4" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> stdout.flush();</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<pre><code>Age: 15
Age: 26
Age: 64</code></pre>
<p>In the above example, we are iterating over the values of the <code>.age</code> array, or, the internal array of the <code>PersonArray</code> object that contains the values of the <code>age</code> data member from the <code>Person</code> values that were added to the multi array struct.</p>
<p>In this example we are calling the <code>items()</code> method directly from the <code>PersonArray</code> object. However, in most situations it’s recommened to call this <code>items()</code> method from a “slice object”, which you can create from the <code>slice()</code> method. The reason for this is that calling <code>items()</code> multiple times have better performance if you use a slice object.</p>
<p>Therefore, if you are planning to access only one of the internal arrays from your “multi array struct”, it’s fine to call <code>items()</code> directly from the multi array object. But if you need to access many of the internal arrays from your “multi array struct”, then, you will likely need to call <code>items()</code> more than once, and, in such circumstance, is better to call <code>items()</code> through a slice object. The example below demonstrates the use of such object:</p>
<div class="cell">
<div class="sourceCode cell-code" id="cb34"><pre class="sourceCode zig code-with-copy"><code class="sourceCode zig"><span id="cb34-1"><a href="#cb34-1" aria-hidden="true" tabindex="-1"></a><span class="kw">var</span> slice = people.slice();</span>
<span id="cb34-2"><a href="#cb34-2" aria-hidden="true" tabindex="-1"></a><span class="kw">for</span> (slice.items(.age)) |*age| <span class="op">{</span></span>
<span id="cb34-3"><a href="#cb34-3" aria-hidden="true" tabindex="-1"></a>    age.* += <span class="dv">10</span>;</span>
<span id="cb34-4"><a href="#cb34-4" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb34-5"><a href="#cb34-5" aria-hidden="true" tabindex="-1"></a><span class="kw">for</span> (slice.items(.name), slice.items(.age)) |*n,*a| <span class="op">{</span></span>
<span id="cb34-6"><a href="#cb34-6" aria-hidden="true" tabindex="-1"></a>    <span class="kw">try</span> stdout.print(</span>
<span id="cb34-7"><a href="#cb34-7" aria-hidden="true" tabindex="-1"></a>        <span class="st">"Name: {s}, Age: {d}</span><span class="sc">\n</span><span class="st">"</span>, .<span class="op">{</span>n.*, a.*<span class="op">}</span></span>
<span id="cb34-8"><a href="#cb34-8" aria-hidden="true" tabindex="-1"></a>    );</span>
<span id="cb34-9"><a href="#cb34-9" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb34-10"><a href="#cb34-10" aria-hidden="true" tabindex="-1"></a><span class="kw">try</span> stdout.flush();</span></code><button title="Copy to Clipboard" class="code-copy-button"><i class="bi"></i></button></pre></div>
</div>
<pre><code>Name: Auguste, Age: 25
Name: Elena, Age: 36
Name: Michael, Age: 74</code></pre>
</section>
<section id="conclusion-1" class="level2" data-number="11.5">
<h2 data-number="11.5" class="anchored" data-anchor-id="conclusion-1"><span class="header-section-number">11.5</span> Conclusion</h2>
<p>There are many other data structures that I haven’t presented here. But you can check them out at the official Zig Standard Library documentation page. Actually, when you get into the <a href="https://ziglang.org/documentation/master/std/#">homepage of the documentation</a><a href="#fn2" class="footnote-ref" id="fnref2" role="doc-noteref"><sup>2</sup></a>, the first thing that appears to you in this page, is a list of types and data structures that are available in the Zig Standard Library. There are some very specific data structures in this list, like a <a href="https://ziglang.org/documentation/master/std/#std.bounded_array.BoundedArray"><code>BoundedArray</code> struct</a><a href="#fn3" class="footnote-ref" id="fnref3" role="doc-noteref"><sup>3</sup></a> , but there is also some more general structures, such as a <a href="https://ziglang.org/documentation/master/std/#std.priority_queue.PriorityQueue"><code>PriorityQueue</code> struct</a><a href="#fn4" class="footnote-ref" id="fnref4" role="doc-noteref"><sup>4</sup></a>.</p>


<div id="refs" class="references csl-bib-body hanging-indent" data-entry-spacing="0" role="list" style="display: none">
<div id="ref-wikipedia_hashtables" class="csl-entry" role="listitem">
Wikipedia. 2024. <span>“Hash Tables.”</span> Wikipedia. <a href="https://en.wikipedia.org/wiki/Hash_table">https://en.wikipedia.org/wiki/Hash_table</a>.
</div>
</div>
</section>
<section id="footnotes" class="footnotes footnotes-end-of-document" role="doc-endnotes">
<hr>
<ol>
<li id="fn1"><p><a href="https://ziglang.org/documentation/master/std/#std.array_list.ArrayListAligned" class="uri">https://ziglang.org/documentation/master/std/#std.array_list.ArrayListAligned</a><a href="#fnref1" class="footnote-back" role="doc-backlink">↩︎</a></p></li>
<li id="fn2"><p><a href="https://ziglang.org/documentation/master/std/#" class="uri">https://ziglang.org/documentation/master/std/#</a><a href="#fnref2" class="footnote-back" role="doc-backlink">↩︎</a></p></li>
<li id="fn3"><p><a href="https://ziglang.org/documentation/master/std/#std.bounded_array.BoundedArray" class="uri">https://ziglang.org/documentation/master/std/#std.bounded_array.BoundedArray</a><a href="#fnref3" class="footnote-back" role="doc-backlink">↩︎</a></p></li>
<li id="fn4"><p><a href="https://ziglang.org/documentation/master/std/#std.priority_queue.PriorityQueue" class="uri">https://ziglang.org/documentation/master/std/#std.priority_queue.PriorityQueue</a>.<a href="#fnref4" class="footnote-back" role="doc-backlink">↩︎</a></p></li>
</ol>
</section>

</main> <!-- /main -->
<script id="quarto-html-after-body" type="application/javascript">
  window.document.addEventListener("DOMContentLoaded", function (event) {
    // Ensure there is a toggle, if there isn't float one in the top right
    if (window.document.querySelector('.quarto-color-scheme-toggle') === null) {
      const a = window.document.createElement('a');
      a.classList.add('top-right');
      a.classList.add('quarto-color-scheme-toggle');
      a.href = "";
      a.onclick = function() { try { window.quartoToggleColorScheme(); } catch {} return false; };
      const i = window.document.createElement("i");
      i.classList.add('bi');
      a.appendChild(i);
      window.document.body.appendChild(a);
    }
    setColorSchemeToggle(hasAlternateSentinel())
    const icon = "";
    const anchorJS = new window.AnchorJS();
    anchorJS.options = {
      placement: 'right',
      icon: icon
    };
    anchorJS.add('.anchored');
    const isCodeAnnotation = (el) => {
      for (const clz of el.classList) {
        if (clz.startsWith('code-annotation-')) {                     
          return true;
        }
      }
      return false;
    }
    const onCopySuccess = function(e) {
      // button target
      const button = e.trigger;
      // don't keep focus
      button.blur();
      // flash "checked"
      button.classList.add('code-copy-button-checked');
      var currentTitle = button.getAttribute("title");
      button.setAttribute("title", "Copied!");
      let tooltip;
      if (window.bootstrap) {
        button.setAttribute("data-bs-toggle", "tooltip");
        button.setAttribute("data-bs-placement", "left");
        button.setAttribute("data-bs-title", "Copied!");
        tooltip = new bootstrap.Tooltip(button, 
          { trigger: "manual", 
            customClass: "code-copy-button-tooltip",
            offset: [0, -8]});
        tooltip.show();    
      }
      setTimeout(function() {
        if (tooltip) {
          tooltip.hide();
          button.removeAttribute("data-bs-title");
          button.removeAttribute("data-bs-toggle");
          button.removeAttribute("data-bs-placement");
        }
        button.setAttribute("title", currentTitle);
        button.classList.remove('code-copy-button-checked');
      }, 1000);
      // clear code selection
      e.clearSelection();
    }
    const getTextToCopy = function(trigger) {
        const codeEl = trigger.previousElementSibling.cloneNode(true);
        for (const childEl of codeEl.children) {
          if (isCodeAnnotation(childEl)) {
            childEl.remove();
          }
        }
        return codeEl.innerText;
    }
    const clipboard = new window.ClipboardJS('.code-copy-button:not([data-in-quarto-modal])', {
      text: getTextToCopy
    });
    clipboard.on('success', onCopySuccess);
    if (window.document.getElementById('quarto-embedded-source-code-modal')) {
      const clipboardModal = new window.ClipboardJS('.code-copy-button[data-in-quarto-modal]', {
        text: getTextToCopy,
        container: window.document.getElementById('quarto-embedded-source-code-modal')
      });
      clipboardModal.on('success', onCopySuccess);
    }
      var localhostRegex = new RegExp(/^(?:http|https):\/\/localhost\:?[0-9]*\//);
      var mailtoRegex = new RegExp(/^mailto:/);
        var filterRegex = new RegExp('/' + window.location.host + '/');
      var isInternal = (href) => {
          return filterRegex.test(href) || localhostRegex.test(href) || mailtoRegex.test(href);
      }
      // Inspect non-navigation links and adorn them if external
     var links = window.document.querySelectorAll('a[href]:not(.nav-link):not(.navbar-brand):not(.toc-action):not(.sidebar-link):not(.sidebar-item-toggle):not(.pagination-link):not(.no-external):not([aria-hidden]):not(.dropdown-item):not(.quarto-navigation-tool):not(.about-link)');
      for (var i=0; i<links.length; i++) {
        const link = links[i];
        if (!isInternal(link.href)) {
          // undo the damage that might have been done by quarto-nav.js in the case of
          // links that we want to consider external
          if (link.dataset.originalHref !== undefined) {
            link.href = link.dataset.originalHref;
          }
        }
      }
    function tippyHover(el, contentFn, onTriggerFn, onUntriggerFn) {
      const config = {
        allowHTML: true,
        maxWidth: 500,
        delay: 100,
        arrow: false,
        appendTo: function(el) {
            return el.parentElement;
        },
        interactive: true,
        interactiveBorder: 10,
        theme: 'quarto',
        placement: 'bottom-start',
      };
      if (contentFn) {
        config.content = contentFn;
      }
      if (onTriggerFn) {
        config.onTrigger = onTriggerFn;
      }
      if (onUntriggerFn) {
        config.onUntrigger = onUntriggerFn;
      }
      window.tippy(el, config); 
    }
    const noterefs = window.document.querySelectorAll('a[role="doc-noteref"]');
    for (var i=0; i<noterefs.length; i++) {
      const ref = noterefs[i];
      tippyHover(ref, function() {
        // use id or data attribute instead here
        let href = ref.getAttribute('data-footnote-href') || ref.getAttribute('href');
        try { href = new URL(href).hash; } catch {}
        const id = href.replace(/^#\/?/, "");
        const note = window.document.getElementById(id);
        if (note) {
          return note.innerHTML;
        } else {
          return "";
        }
      });
    }
    const xrefs = window.document.querySelectorAll('a.quarto-xref');
    const processXRef = (id, note) => {
      // Strip column container classes
      const stripColumnClz = (el) => {
        el.classList.remove("page-full", "page-columns");
        if (el.children) {
          for (const child of el.children) {
            stripColumnClz(child);
          }
        }
      }
      stripColumnClz(note)
      if (id === null || id.startsWith('sec-')) {
        // Special case sections, only their first couple elements
        const container = document.createElement("div");
        if (note.children && note.children.length > 2) {
          container.appendChild(note.children[0].cloneNode(true));
          for (let i = 1; i < note.children.length; i++) {
            const child = note.children[i];
            if (child.tagName === "P" && child.innerText === "") {
              continue;
            } else {
              container.appendChild(child.cloneNode(true));
              break;
            }
          }
          if (window.Quarto?.typesetMath) {
            window.Quarto.typesetMath(container);
          }
          return container.innerHTML
        } else {
          if (window.Quarto?.typesetMath) {
            window.Quarto.typesetMath(note);
          }
          return note.innerHTML;
        }
      } else {
        // Remove any anchor links if they are present
        const anchorLink = note.querySelector('a.anchorjs-link');
        if (anchorLink) {
          anchorLink.remove();
        }
        if (window.Quarto?.typesetMath) {
          window.Quarto.typesetMath(note);
        }
        if (note.classList.contains("callout")) {
          return note.outerHTML;
        } else {
          return note.innerHTML;
        }
      }
    }
    for (var i=0; i<xrefs.length; i++) {
      const xref = xrefs[i];
      tippyHover(xref, undefined, function(instance) {
        instance.disable();
        let url = xref.getAttribute('href');
        let hash = undefined; 
        if (url.startsWith('#')) {
          hash = url;
        } else {
          try { hash = new URL(url).hash; } catch {}
        }
        if (hash) {
          const id = hash.replace(/^#\/?/, "");
          const note = window.document.getElementById(id);
          if (note !== null) {
            try {
              const html = processXRef(id, note.cloneNode(true));
              instance.setContent(html);
            } finally {
              instance.enable();
              instance.show();
            }
          } else {
            // See if we can fetch this
            fetch(url.split('#')[0])
            .then(res => res.text())
            .then(html => {
              const parser = new DOMParser();
              const htmlDoc = parser.parseFromString(html, "text/html");
              const note = htmlDoc.getElementById(id);
              if (note !== null) {
                const html = processXRef(id, note);
                instance.setContent(html);
              } 
            }).finally(() => {
              instance.enable();
              instance.show();
            });
          }
        } else {
          // See if we can fetch a full url (with no hash to target)
          // This is a special case and we should probably do some content thinning / targeting
          fetch(url)
          .then(res => res.text())
          .then(html => {
            const parser = new DOMParser();
            const htmlDoc = parser.parseFromString(html, "text/html");
            const note = htmlDoc.querySelector('main.content');
            if (note !== null) {
              // This should only happen for chapter cross references
              // (since there is no id in the URL)
              // remove the first header
              if (note.children.length > 0 && note.children[0].tagName === "HEADER") {
                note.children[0].remove();
              }
              const html = processXRef(null, note);
              instance.setContent(html);
            } 
          }).finally(() => {
            instance.enable();
            instance.show();
          });
        }
      }, function(instance) {
      });
    }
        let selectedAnnoteEl;
        const selectorForAnnotation = ( cell, annotation) => {
          let cellAttr = 'data-code-cell="' + cell + '"';
          let lineAttr = 'data-code-annotation="' +  annotation + '"';
          const selector = 'span[' + cellAttr + '][' + lineAttr + ']';
          return selector;
        }
        const selectCodeLines = (annoteEl) => {
          const doc = window.document;
          const targetCell = annoteEl.getAttribute("data-target-cell");
          const targetAnnotation = annoteEl.getAttribute("data-target-annotation");
          const annoteSpan = window.document.querySelector(selectorForAnnotation(targetCell, targetAnnotation));
          const lines = annoteSpan.getAttribute("data-code-lines").split(",");
          const lineIds = lines.map((line) => {
            return targetCell + "-" + line;
          })
          let top = null;
          let height = null;
          let parent = null;
          if (lineIds.length > 0) {
              //compute the position of the single el (top and bottom and make a div)
              const el = window.document.getElementById(lineIds[0]);
              top = el.offsetTop;
              height = el.offsetHeight;
              parent = el.parentElement.parentElement;
            if (lineIds.length > 1) {
              const lastEl = window.document.getElementById(lineIds[lineIds.length - 1]);
              const bottom = lastEl.offsetTop + lastEl.offsetHeight;
              height = bottom - top;
            }
            if (top !== null && height !== null && parent !== null) {
              // cook up a div (if necessary) and position it 
              let div = window.document.getElementById("code-annotation-line-highlight");
              if (div === null) {
                div = window.document.createElement("div");
                div.setAttribute("id", "code-annotation-line-highlight");
                div.style.position = 'absolute';
                parent.appendChild(div);
              }
              div.style.top = top - 2 + "px";
              div.style.height = height + 4 + "px";
              div.style.left = 0;
              let gutterDiv = window.document.getElementById("code-annotation-line-highlight-gutter");
              if (gutterDiv === null) {
                gutterDiv = window.document.createElement("div");
                gutterDiv.setAttribute("id", "code-annotation-line-highlight-gutter");
                gutterDiv.style.position = 'absolute';
                const codeCell = window.document.getElementById(targetCell);
                const gutter = codeCell.querySelector('.code-annotation-gutter');
                gutter.appendChild(gutterDiv);
              }
              gutterDiv.style.top = top - 2 + "px";
              gutterDiv.style.height = height + 4 + "px";
            }
            selectedAnnoteEl = annoteEl;
          }
        };
        const unselectCodeLines = () => {
          const elementsIds = ["code-annotation-line-highlight", "code-annotation-line-highlight-gutter"];
          elementsIds.forEach((elId) => {
            const div = window.document.getElementById(elId);
            if (div) {
              div.remove();
            }
          });
          selectedAnnoteEl = undefined;
        };
          // Handle positioning of the toggle
      window.addEventListener(
        "resize",
        throttle(() => {
          elRect = undefined;
          if (selectedAnnoteEl) {
            selectCodeLines(selectedAnnoteEl);
          }
        }, 10)
      );
      function throttle(fn, ms) {
      let throttle = false;
      let timer;
        return (...args) => {
          if(!throttle) { // first call gets through
              fn.apply(this, args);
              throttle = true;
          } else { // all the others get throttled
              if(timer) clearTimeout(timer); // cancel #2
              timer = setTimeout(() => {
                fn.apply(this, args);
                timer = throttle = false;
              }, ms);
          }
        };
      }
        // Attach click handler to the DT
        const annoteDls = window.document.querySelectorAll('dt[data-target-cell]');
        for (const annoteDlNode of annoteDls) {
          annoteDlNode.addEventListener('click', (event) => {
            const clickedEl = event.target;
            if (clickedEl !== selectedAnnoteEl) {
              unselectCodeLines();
              const activeEl = window.document.querySelector('dt[data-target-cell].code-annotation-active');
              if (activeEl) {
                activeEl.classList.remove('code-annotation-active');
              }
              selectCodeLines(clickedEl);
              clickedEl.classList.add('code-annotation-active');
            } else {
              // Unselect the line
              unselectCodeLines();
              clickedEl.classList.remove('code-annotation-active');
            }
          });
        }
    const findCites = (el) => {
      const parentEl = el.parentElement;
      if (parentEl) {
        const cites = parentEl.dataset.cites;
        if (cites) {
          return {
            el,
            cites: cites.split(' ')
          };
        } else {
          return findCites(el.parentElement)
        }
      } else {
        return undefined;
      }
    };
    var bibliorefs = window.document.querySelectorAll('a[role="doc-biblioref"]');
    for (var i=0; i<bibliorefs.length; i++) {
      const ref = bibliorefs[i];
      const citeInfo = findCites(ref);
      if (citeInfo) {
        tippyHover(citeInfo.el, function() {
          var popup = window.document.createElement('div');
          citeInfo.cites.forEach(function(cite) {
            var citeDiv = window.document.createElement('div');
            citeDiv.classList.add('hanging-indent');
            citeDiv.classList.add('csl-entry');
            var biblioDiv = window.document.getElementById('ref-' + cite);
            if (biblioDiv) {
              citeDiv.innerHTML = biblioDiv.innerHTML;
            }
            popup.appendChild(citeDiv);
          });
          return popup.innerHTML;
        });
      }
    }
  });
  </script>
<nav class="page-navigation">
  <div class="nav-page nav-page-previous">
      <a href="../Chapters/09-error-handling.html" class="pagination-link" aria-label="Error handling and unions">
        <i class="bi bi-arrow-left-short"></i> <span class="nav-page-text"><span class="chapter-number">10</span>&nbsp; <span class="chapter-title">Error handling and unions</span></span>
      </a>          
  </div>
  <div class="nav-page nav-page-next">
      <a href="../Chapters/10-stack-project.html" class="pagination-link" aria-label="Project 3 - Building a stack data structure">
        <span class="nav-page-text"><span class="chapter-number">12</span>&nbsp; <span class="chapter-title">Project 3 - Building a stack data structure</span></span> <i class="bi bi-arrow-right-short"></i>
      </a>
  </div>
</nav>
</div> <!-- /content -->




</body></html>